Date：2022.02.13
题意：
一个迷宫可以看作一个 R 行 C 列的方格矩阵。
其中一些方格是空地，用 . 表示，其他方格是障碍，用 # 表示。
开始时，乔位于一块空地之中。
迷宫中一些空地已经起火了，幸运的是火还没有蔓延至乔所在的位置。
为了避免被火烧伤，乔需要尽快逃离迷宫。
已知，乔每单位时间只能沿上下左右四个方向前进一格距离，并且在前进过程中，他不能进入障碍方格。
火每单位时间都会蔓延至其上下左右四个方向的相邻空地，但是火也会被障碍阻挡。
如果一个方格已经起火或者会在乔进入方格的那一时刻恰好起火，则该方格很危险，乔不能进入。
当乔进入到任意一个位于边界的空地方格时，他都可以再花费一单位时间，直接逃离迷宫。
请问，乔想要逃离迷宫，最少需要花费的时间。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含两个整数 R,C。
接下来 R 行，包含一个 R×C 的字符矩阵。
矩阵中只包含以下四种字符：
# 表示障碍方格。
. 表示空地方格。
J 表示乔所在的空地方格，最多只有一个。
F 表示已经起火的空地方格。
输出格式
每组数据输出一行结果，一个整数表示逃离迷宫所需花费的最少时间，如果无法逃离迷宫，则输出 IMPOSSIBLE。
数据范围
1≤T≤10,
1≤R,C≤1000。
输入样例：
2
4 4

#JF#
#…#
#…#
3 3

#J.
#.F
输出样例：
3
IMPOSSIBLE

思路：对火做一遍bfs，再对人做一遍bfs，对人做时标记到每个块的最小长度，如果最小长度严格小于火到这里的最小长度，则可以走到该格子；否则不行。【注意火可能有多个点，初始化注意。】
代码如下：

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1010;
char c[N][N];
typedef long long LL;
typedef pair<LL, LL> PII;
LL t,n,m,dr[N][N],dh[N][N],rx,ry;
vector<PII>v;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs()
{memset(dh,-1,sizeof dh);memset(dr,-1,sizeof dr);queue<PII>qr,qh;qr.push({rx,ry});dr[rx][ry]=0;for(int i=0;i<v.size();i++) {qh.push({v[i].x,v[i].y});dh[v[i].x][v[i].y]=0;}while(qh.size()){PII t=qh.front();qh.pop();for(int i=0;i<4;i++){LL ix=t.x+dx[i],iy=t.y+dy[i];if(ix<=0||iy<=0||ix>n||iy>m||c[ix][iy]=='#'||dh[ix][iy]!=-1) continue;qh.push({ix,iy});dh[ix][iy]=dh[t.x][t.y]+1;}}while(qr.size()){PII t=qr.front();qr.pop();for(int i=0;i<4;i++){LL ix=t.x+dx[i],iy=t.y+dy[i];if(ix<=0||iy<=0||ix>n||iy>m||c[ix][iy]=='#'||dr[ix][iy]!=-1) continue;dr[ix][iy]=dr[t.x][t.y]+1;if(dh[ix][iy]<=dr[ix][iy]) dr[ix][iy]=-1;else qr.push({ix,iy});}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n>>m;v.clear();for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {cin>>c[i][j];if(c[i][j]=='J') {rx=i;ry=j;}if(c[i][j]=='F') v.push_back({i,j});}bfs();LL minn=1e18;for(int j=1;j<=m;j++){if(dr[1][j]>-1) minn=min(minn,dr[1][j]);if(dr[n][j]>-1) minn=min(minn,dr[n][j]);}for(int i=1;i<=n;i++){if(dr[i][1]>-1) minn=min(minn,dr[i][1]);if(dr[i][m]>-1) minn=min(minn,dr[i][m]);}if(minn==1e18) cout<<"IMPOSSIBLE"<<endl;else cout<<minn+1<<endl;}return 0;
}