2147: 미로 탈출하기(BFS)
[만든사람 : ]
문제 설명
N x M 크기의 미로가 있다. 맨 처음은(1,1)위치에서 시작한다.
몬스터가 있는 곳은 0, 몬스터가 없는 곳은 1로 표시된다.
몬스터를 피해서 (1,1) 좌표에서 (N,M) 좌표까지 탈출해야한다.
이때 탈출까지의 최단 거리를 구하여라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
몬스터가 있는 곳은 0, 몬스터가 없는 곳은 1로 표시된다.
몬스터를 피해서 (1,1) 좌표에서 (N,M) 좌표까지 탈출해야한다.
이때 탈출까지의 최단 거리를 구하여라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
입력 설명
첫 째 줄에 두 정수 N,M(4<=N,M<=200)이 주어진다.
다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다.
각각의 수들은 공백없이 붙어서 입력되며, 시작 칸과 마지막 칸은 항상 1이다.
다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다.
각각의 수들은 공백없이 붙어서 입력되며, 시작 칸과 마지막 칸은 항상 1이다.
출력 설명
첫째 줄에 최소 이동 칸의 개수를 출력한다.
입력 예시 Copy
5 6
101010
111111
000001
111111
111111
출력 예시 Copy
10