시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 293 63 41 18.636%

문제

지훈이는 미로에서 일을 한다. 불행히도, 미로의 일부가 불에 붙었고 미로 주인은 게을러서 비상대피로를 만들지 않았다.

지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다)  이동한다. 

불은 각 지점에서 네 방향으로 확산된다. 

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1<= R,C <= 1000

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

  • #: 벽
  • .: 지나갈 수 있는 공간
  • J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
  • F: 불이난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는경우에는 가장 빠른 탈출시간을 출력한다. 

예제 입력

4 4
####
#JF#
#..#
#..#

예제 출력

3

힌트

출처

Contest > Waterloo's local Programming Contests > 13 June, 2009 B번

  • 잘못된 번역을 찾은 사람: jh05013
  • 문제를 번역한 사람: lyzqm