Fire!

Interview

Time limit1sMemory limit256 MB

Summary

Given a grid with walls, one starting cell, and burning cells, find the earliest minute Jihoon can step off the edge, given the fire spreads one cell per minute.

Level: Medium6 of 10
Topics: BFS, Graph, Simulation, Matrix
Solved: No attempts yet

Problem

Jihoon is trapped inside a maze, and a fire is spreading through it. Determine whether Jihoon can escape the maze before the fire reaches him, and if so, the earliest time at which he can escape.

Each minute, both Jihoon and the fire move one cell in one of the four orthogonal directions (never diagonally). Each minute, the fire spreads from every burning cell to its four neighbouring cells. Neither Jihoon nor the fire can move through walls. Jihoon cannot move into a cell that is already on fire or that the fire spreads into during the same minute.

Jihoon escapes by moving out of the maze from a cell on its edge: if Jihoon is on an edge cell at some minute, he can move outside on the next minute. Jihoon starts at his initial position at minute 0.

Input

The first line contains two integers $R$ and $C$ separated by a space ( $1 \le R, C \le 1000$ ), where $R$ is the number of rows and $C$ the number of columns of the maze.

Each of the following $R$ lines gives one row of the maze. The characters mean:

#: a wall
.: a passable empty cell
J: Jihoon's starting position (a passable cell)
F: a cell that is on fire

Exactly one J appears in the input.

Output

If Jihoon cannot escape the maze before the fire reaches him, print IMPOSSIBLE. Otherwise, print the earliest escape time (the minute at which Jihoon moves out of the maze).

Examples3

Example 1
Input
```
4 4
####
#JF#
#..#
#..#
```
Expected output
```
3
```
Example 2
Input
```
3 3
J..
...
..F
```
Expected output
```
1
```
Example 3
Input
```
3 3
###
#J#
###
```
Expected output
```
IMPOSSIBLE
```