백준 2178 미로탐색

백준 2178

#include<bits/stdc++.h>
using namespace std;
string arr[101];
int vis[101][101];
int n, m, cnt;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	queue<pair<int, int>>q;

	q.push({ 0,0 });
	vis[0][0] = 1;

	while(!q.empty()) {

		pair<int, int> nxt = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = nxt.first+dx[i];
			int ny = nxt.second+dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (!vis[nx][ny] && arr[nx][ny] == '1') {
				vis[nx][ny] = vis[nxt.first][nxt.second] + 1;
				q.push({ nx,ny });
			}
			
		}
	}
	cout << vis[n - 1][m - 1] << '\n';
}