[2178] 미로탐색

풀이

기본적인 BFS를 구현하면 된다.

//가로세로
4 6
//맵 입력
101111
101010
101011
111011
//경로 구하기
1 0 9 10 11 12
2 0 8 0 12 0
3 0 7 0 13 14
4 5 6 0 14 15
//답
15

코드

#include <cstdio>
#include <queue>
using namespace std;
int map[101][101];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
bool check[101][101];
int n = 0, m = 0;

void bfs(int x, int y) {
	queue<pair<int, int> > q;
	q.push(make_pair(x, y));
	int nx = 0, ny = 0;
	while (!q.empty()) {
		pair<int, int> f = q.front(); q.pop();
		check[f.first][f.second] = true;
		for (int k = 0; k < 4; k++) {
			nx = f.first + dx[k];
			ny = f.second + dy[k];
			if (nx < 0 || nx > n) continue;
			if (ny < 0 || ny > m) continue;
			if (map[nx][ny] != 0 && check[nx][ny] == false) {
				map[nx][ny] = map[f.first][f.second] + 1;
				check[nx][ny] = true;
				q.push(make_pair(nx, ny));
			}
		}
	}
}

int main(void) {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	bfs(0,0);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			printf("%d ", map[i][j]);
		}
		printf("\n");
	}
	printf("%d\n", map[n-1][m-1]);
	return 0;
}