백준 2178 (미로 탐색)

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

N by M크기의 미로가 주어지며 시작점이 1 by 1 의 위치일 때 N by M 의 위치에 도달하기 까지 걸리는 최소 이동 횟수를 구하는 문제이다. 

#include <iostream>
#include <string>
#include <queue>

using namespace std;
struct Node{
	int y, x;
	int cnt;
};

int n, m;
int checkY[4] = { 0, 0, 1, -1 };
int checkX[4] = { 1, -1, 0, 0 };

string map[101];
int visit[101][101];

void bfs(int y, int x){
	queue<Node> qu;
	visit[y][x] = 1;
	qu.push({ y, x, 1 });

	while (!qu.empty()){
		Node now = qu.front();
		if (now.y == n - 1 && now.x == m - 1) cout << now.cnt << endl;
		for (int i = 0; i < 4; ++i){
			int dy = now.y + checkY[i];
			int dx = now.x + checkX[i];
			if (dy < 0 || dx < 0 || dy >= n || dx >= m) continue;
			if (map[dy][dx] == '0' || visit[dy][dx] == 1) continue;
			visit[dy][dx] = 1;
			qu.push({ dy, dx, now.cnt + 1 });
		}
		qu.pop();
	}
	return;
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n >> m;

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

	bfs(0, 0);

}