불!
면접 대비시간 제한1초메모리 제한256 MB
벽과 시작 위치, 불타는 칸이 있는 격자에서 불이 매분 한 칸씩 번질 때 지훈이가 가장 빨리 격자 밖으로 나갈 수 있는 시각을 구한다.
문제
지훈이는 미로 안에 갇혀 있고, 미로에는 불이 번지고 있다. 지훈이가 불에 타기 전에 미로에서 탈출할 수 있는지, 탈출할 수 있다면 가장 빠른 탈출 시간이 언제인지 구하자.
지훈이와 불은 매 분마다 상하좌우로 인접한 칸으로 한 칸씩 이동한다(대각선으로는 이동하지 않는다). 불은 매 분마다 불이 붙어 있는 모든 칸에서 네 방향의 이웃 칸으로 번진다. 지훈이와 불은 모두 벽이 있는 칸을 지나갈 수 없다. 지훈이는 이미 불이 붙어 있거나 이번 분에 불이 옮겨붙는 칸으로는 이동할 수 없다.
지훈이는 미로의 가장자리에 있는 칸에서 미로 밖으로 나가 탈출한다. 지훈이가 어떤 분에 가장자리 칸에 있으면, 그다음 분에 미로 밖으로 나갈 수 있다. 지훈이는 0분에 시작 위치에 있다.
입력
첫째 줄에 공백으로 구분된 두 정수 과 가 주어진다 (). 은 미로의 행 개수, 는 열 개수이다.
이어지는 개의 줄에 미로의 각 행이 주어진다. 각 문자의 의미는 다음과 같다.
#: 벽.: 지나갈 수 있는 빈 칸J: 지훈이의 시작 위치 (지나갈 수 있는 칸이다)F: 불이 난 칸
J는 입력에 정확히 하나만 주어진다.
출력
지훈이가 불이 닿기 전에 미로를 탈출할 수 없으면 IMPOSSIBLE을 출력한다. 탈출할 수 있으면 가장 빠른 탈출 시간(지훈이가 미로 밖으로 나가는 분)을 출력한다.