题目链接:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2671
Time limit: 1.000 seconds

Description

Joe works in a maze. Unfortunately, portions of the maze have caught on fire, and the owner of the maze neglected to create a fire escape plan. Help Joe escape the maze.

Given Joe’s location in the maze and which squares of the maze are on fire, you must determine whether Joe can exit the maze before the fire reaches him, and how fast he can do it.

Joe and the fire each move one square per minute, vertically or horizontally (not diagonally). The fire spreads all four directions from each square that is on fire. Joe may exit the maze from any square that borders the edge of the maze. Neither Joe nor the fire may enter a square that is occupied by a wall.

Input

The first line of input contains the two integers R and C, separated by spaces, with 1≤R,C≤1000. The following R lines of input each contain one row of the maze. Each of these lines contains exactly C characters, and each of these characters is one of:

  • #, a wall

  • ., a passable square

  • J, Joe’s initial position in the maze, which is a passable square

  • F, a square that is on fire

There will be exactly one J in the input.

Output

Output a single line containing “IMPOSSIBLE” if Joe cannot exit the maze before the fire reaches him, or an integer giving the earliest time Joe can safely exit the maze, in minutes.

Sample Input

2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F

Sample Output

3
IMPOSSIBLE

Problem solving report:

Description: 在一个迷宫里有一个人和一堆火，这个人和火都可以在一个单位时间内移动到与其相邻的上下左右的方格中，p判断这个人能否在火势蔓延到自己所在方格之前离开这个方格，是否可以成功逃生(就是走到迷宫之)。如果可以输出最少的时间
，否则输出"IMPOSSIBLE"。
Problem solving: 需要两次BFS，因为火出现位置和蔓延方向固定，所以何时何地会被火覆盖是固定的，只要先进行预处理得到某处在多长时间后会被大火覆盖，在进行BFS时经过某点时间小于这个时间就OK了，注意火不止一个。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int inf = 0x3f3f3f3f;
char mp[MAXN][MAXN];
int r, c, spt[MAXN][MAXN];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
struct edge {
    int x, y, t;
    edge(int x_, int y_, int t_) {
        x = x_, y = y_, t = t_;
    }
}p(0, 0, 0);
queue <edge> Q;
void BFS() {
    int tx, ty;
    while (!Q.empty()) {
        p = Q.front();
        Q.pop();
        for (int i = 0; i < 4; i++) {
            tx = p.x + dir[i][0];
            ty = p.y + dir[i][1];
            if (tx >= 0 && tx < r && ty >= 0 && ty < c && mp[tx][ty] != '#' && spt[tx][ty] > p.t + 1) {
                spt[tx][ty] = p.t + 1;
                Q.push(edge(tx, ty, p.t + 1));
            }
        }
    }
}
int BFS(int x, int y) {
    int tx, ty;
    mp[x][y] = '#';
    Q.push(edge(x, y, 0));
    while (!Q.empty()) {
        p = Q.front();
        Q.pop();
        if (!(p.x && p.x != r - 1 && p.y && p.y != c - 1))
            return p.t + 1;
        for (int i = 0; i < 4; i++) {
            tx = p.x + dir[i][0];
            ty = p.y + dir[i][1];
            if (tx >= 0 && tx < r && ty >= 0 && ty < c && mp[tx][ty] != '#' && p.t + 1 < spt[tx][ty]) {
                mp[tx][ty] = '#';
                Q.push(edge(tx, ty, p.t + 1));
            }
        }
    }
    return -1;
}
int main() {
    int t, ex, ey;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &r, &c);
        memset(spt, 0x3f, sizeof(spt));
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                scanf(" %c", &mp[i][j]);
                if (mp[i][j] == 'F') {
                    spt[i][j] = 0;
                    Q.push(edge(i, j, 0));
                }
                else if (mp[i][j] == 'J')
                    ex = i, ey = j;
            }
        }
        BFS();
        int ans = BFS(ex, ey);
        if (~ans)
            printf("%d\n", ans);
        else printf("IMPOSSIBLE\n");
        while (!Q.empty())
            Q.pop();
    }
    return 0;
}