6129 : 탈출 경로 최적
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
여러 개의 출구 'E'가 존재하는 N×M 크기의 격자 미로가 주어집니다. 0은 지나갈 수 있는 빈칸, 1은 지나갈 수 없는 벽, 'J'는 지수의 임의 시작 위치입니다.
지수가 현재 위치 (r, c)에서 출발하여 가장 가까운 출구까지 탈출하는 데 걸리는 최단 시간을 구하십시오. 시작지점이 이미 출구라면 0을 출력합니다.
지수가 현재 위치 (r, c)에서 출발하여 가장 가까운 출구까지 탈출하는 데 걸리는 최단 시간을 구하십시오. 시작지점이 이미 출구라면 0을 출력합니다.
입력 설명
첫째 줄에 격자의 세로 크기 N과 가로 크기 M (1 ≤ N, M ≤ 1,000)이 주어집니다.
둘째 줄부터 N개의 줄에 격자 정보가 주어집니다. (0, 1, E, J가 공백 구분되어 주어집니다.)
마지막 줄에는 시작 위치 r, c가 주어집니다. (0-indexed)
둘째 줄부터 N개의 줄에 격자 정보가 주어집니다. (0, 1, E, J가 공백 구분되어 주어집니다.)
마지막 줄에는 시작 위치 r, c가 주어집니다. (0-indexed)
출력 설명
가장 가까운 출구까지의 최단 거리를 출력합니다. 탈출이 불가능하면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0 1 E
0 1 0
J 0 0
2 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
시작지점 한 곳에서 탐색하는 것보다, 격자 내의 모든 출구 'E'를 큐에 먼저 한꺼번에 넣고 시작하는 역방향 다중 소스 BFS를 수행하면 한 번의 탐색으로 지수의 위치까지 도달하는 최단 거리를 빠르게 도출할 수 있습니다.