一个迷宫可以看作一个 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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, INF = 0x3f3f3f3f;
int n, m;
char g[N][N];
int d[N][N], w[N][N];
vector<PII> fire;
void bfs()
{
queue<PII> q;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
for (auto& [x, y] : fire)
q.push({x, y}), d[x][y] = 0;
while (q.size())
{
PII t = q.front();
q.pop();
for (int i = 0; i < 4; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 1 || a > n || b < 1 || b > m) continue;
if (d[a][b] != INF || g[a][b] != '.') continue;
d[a][b] = d[t.x][t.y] + 1;
q.push({a, b});
}
}
}
int BFS(int sx, int sy)
{
if (sx == 1 || sx == n || sy == 1 || sy == m) return 1;
queue<PII> q;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
q.push({sx, sy});
w[sx][sy] = 0;
while (q.size())
{
PII t = q.front();
q.pop();
for (int i = 0; i < 4; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 1 || a > n || b < 1 || b > m) continue;
if (w[a][b] != INF|| g[a][b] != '.' || w[t.x][t.y] + 1 >= d[a][b]) continue;
w[a][b] = w[t.x][t.y] + 1;
if (a == 1 || a == n || b == 1 || b == m) return w[a][b] + 1;
q.push({a, b});
}
}
return -1;
}
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> g[i] + 1;
fire.clear();
memset(d, 0x3f, sizeof d);
memset(w, 0x3f, sizeof w);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (g[i][j] == 'F') fire.push_back({i, j});
bfs();
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (g[i][j] == 'J')
{
int res = BFS(i, j);
if (res == -1) puts("IMPOSSIBLE");
else cout << res << endl;
break;
}
}
return 0;
}
