백준 2178번: 미로탐색 (bfs 이용)

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

2178번: 미로 탐색

 

#include <stdio.h>

int queue[10001][2] = { 0, };
int front = 0, rear = 0;

int maze[101][101] = { 0, };
int n = 0, m = 0;

int bfs() {
	int dx[4] = { -1, 1, 0, 0 };
	int dy[4] = { 0, 0, -1, 1 };

	queue[rear][0] = 1;
	queue[rear++][1] = 1;

	while (front < rear) {
		int x = queue[front][0];
		int y = queue[front++][1];

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx<1 || ny<1 || nx>n || ny>m)
				continue;

			if (maze[nx][ny] != 1)
				continue;

			maze[nx][ny] = maze[x][y] + 1;
			queue[rear][0] = nx;
			queue[rear++][1] = ny;
		}
	}
	return maze[n][m];
}

int main() {
	scanf("%d %d", &n, &m);
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%1d", &maze[i][j]);

	int ans = bfs();
	printf("%d", ans);

	return 0;
}