6117 : 불! (두 BFS)
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
미로가 주어집니다. 미로에는 지수('J')와 불('F')이 존재합니다. 불은 매 초마다 상하좌우 인접한 빈칸으로 동시에 확산되며, 지수 역시 매 초마다 상하좌우로 1칸 이동합니다. 벽('#')은 지나갈 수 없습니다.
지수가 불에 탈 가능성이 있는 경로를 배제하고 미로의 가장자리 바깥으로 무사히 탈출할 수 있는 가장 빠른 시간을 구하시오.
지수가 불에 탈 가능성이 있는 경로를 배제하고 미로의 가장자리 바깥으로 무사히 탈출할 수 있는 가장 빠른 시간을 구하시오.
입력 설명
첫째 줄에 행의 개수 R과 열의 개수 C (1 ≤ R, C ≤ 1,000)가 주어집니다.
둘째 줄부터 R개의 줄에 미로 정보가 한 줄씩 주어집니다.
둘째 줄부터 R개의 줄에 미로 정보가 한 줄씩 주어집니다.
출력 설명
지수가 탈출할 수 있는 최소 시간을 출력합니다. 탈출이 불가능하다면
IMPOSSIBLE을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
####
#JF#
#..#
####
출력 예시
COPY
복사되었습니다!
복사되었습니다!
IMPOSSIBLE도움
불에 대한 BFS를 먼저 전역으로 돌려 각 칸에 불이 도달하는 시간을 계산해둔 뒤, 지수에 대한 BFS를 수행할 때 지수가 도달하는 시간이 그 칸의 불 도달 시간보다 엄격히 작은 경우에만 이동하도록 조건을 추가하십시오.