1167 - 불이야!!

Time Limit: 1s Memory Limit: 128MB

Submissions: 56 Solved: 10

Description

술을 잔뜩 먹어서 결국 길에서 잠들어버린 Jungmin은 정신을 차려보니 지금 미로에 갇혔다는 사실을 깨달았다. 불행히도, 미로 곳곳에 불이 난 곳이 있다. 불씨는 조금씩 퍼지면서 Jungmin이 탈출할 퇴로를 막으려 할 것이다. Jungmin은 과연 이 미로를 탈출할 수 있을까?

Jungmin의 이동속도와 불씨가 퍼지는 속도는 같다. 둘다 1분에 격자상의 4방향으로 한 칸씩 움직일 수 있다.(대각선은 아니다.) 불씨는 1분뒤 현재 자기위치 주변의 4곳 모두에 불씨를 퍼트린다.

Jungmin이 주어진 미로의 바깥으로 도달한 순간이 탈출한 순간이다.

Input

입력의 첫째줄에는 미로의 가로세로를 나타내는 r c가 주어진다. (1 <= r, c <= 1,000)

그 다음 r줄에 걸쳐 미로의 정보가 주어진다. 각 줄에는 정확히 c개의 문자가 있으며, 그 문자는 다음 4개중 하나이다.

'#' 은 벽이다. 불씨와 Jungmin 모두 이곳을 지나갈 수 없다.
'.' 은 길이다. 불씨와 Jungmin 모두 이곳을 지나갈 수 있다.
'J' 은 Jungmin의 위치이다. 길로 취급한다.
'F' 는 불씨의 위치이다.

미로에 J는 정확히 하나가 존재한다.

I

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

II

3 3
###
#J.
#.F

Output

탈출이 가능하다면 탈출하는데 걸리는 최소시간을, 불가능하다면 IMPOSSIBLE을 출력한다.

I

II

IMPOSSIBLE

Sample Input

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

Sample Output