7131 : 미로 탈출 최단
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N × M 격자 미로에서 시작 위치 S에서 종료 위치 E까지 가기 위한 최단 거리를 구하십시오.
격자에서 0은 빈 공간이고 1은 이동할 수 없는 벽입니다. 상하좌우로만 움직일 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
격자에서 0은 빈 공간이고 1은 이동할 수 없는 벽입니다. 상하좌우로만 움직일 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 N과 M이 공백으로 구분되어 주어집니다. (2 ≤ N, M ≤ 100)
둘째 줄부터 N개의 줄에 걸쳐 미로의 격자 상태(S, E, 0, 1)가 공백으로 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 미로의 격자 상태(S, E, 0, 1)가 공백으로 구분되어 주어집니다.
출력 설명
시작 위치에서 종료 위치까지의 최단 거리를 정수로 출력합니다. 도달할 수 없는 경우 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
S 0 0
1 1 0
1 1 E
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
미로 탐색의 전형적인 BFS 문제입니다. 큐에
(r, c, dist)를 넣고 한 칸씩 전진해가며 목적지에 도달하는 시점의 dist를 반환합니다.