88. 미로의 최단거리 통로(BFS)

문제

7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요. 경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈 출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위와 같은 경로가 최단 경로이며 경로수는 12이다.

입력설명

첫 번째 줄부터 7*7 격자의 정보가 주어집니다.

출력설명

첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.

입력예제

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0

출력예제

12

---

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int map[10][10], distances[10][10];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
struct Location{
	int x;
	int y;
	Location(int a, int b){
		x = a;
		y = b;
	}
};
queue<Location> Q;

int main(){
	freopen("input.txt", "rt", stdin);
	int i, j;
	for(i=1; i<=7; i++){
		for(j=1; j<=7; j++){
			scanf("%d", &map[i][j]);
		}
	}
	Q.push(Location(1, 1));
	map[1][1] = 1;
	while(!Q.empty()){
		Location temp = Q.front();
		Q.pop();
		for(i=0; i<4; i++){
			int xx = temp.x + dx[i];
			int yy = temp.y + dy[i];
			if(map[xx][yy] == 0 && xx>=1 && xx<=7 && yy>=1 && yy<=7){
				Q.push(Location(xx, yy));
				map[xx][yy] = 1;
				distances[xx][yy] = distances[temp.x][temp.y] + 1;
			}
		}
	}
	printf("%d", distances[7][7]);
	
	return 0;
}