题意：joe在一个迷宫里，迷宫的一些部分着火了，火势会向周围四个方向蔓延，joe可以向四个方向移动。火与人的速度都是1格/1秒，问j能否逃出迷宫，若能输出最小时间。
题解：先考虑模拟火，肯定是bfs（每次把同一时间着火的格子pop出来，再将它们周围的格子的t加一push进去）
然后考虑怎么模拟人，现在人处在一个会变化的迷宫中。貌似很复杂。
我们可以考虑t时刻的地图（假设我们bfs人的位置），着火的地方相当于墙壁，已经走过的地方也相当于墙壁（因为不可能回到已经走过的地方，这样要么出不去，要么走了回头路导致时间变长）。队列中存着当前时刻所有人可以到达的位置。考虑我们可以走的位置，除了边界与墙壁，如果我们知到一秒后哪些位置会着火，我们就不会走那些格子（否则就烧死了）。
于是便得到了一个算法，先让火烧一秒，然后人bjs一步，再烧1秒，再走一步。。。。
坑：一开始我先让人走一步，结果完全无法模拟人被火烧到的情况；
用queue的的时候老报错，总是pop空栈（因为没有考虑第一个与同一时刻的最后一个的特殊情况，结果写了一个很混乱的逻辑判断）
正确的方法是:
f v = F.front();
if (v.t == t) {...} else{return;}
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = + ;
//模拟F，深搜J，
//F有多个，J一个
struct f {
int x, y, t;
f(int x = , int y = , int t = ) :x(x), y(y), t(t) {}
};
int dir[][] = { ,, ,-, ,, -, };
char map[maxn][maxn];
int vis[maxn][maxn], fired[maxn][maxn];
queue<f > F, J;
int R, C; int flag = ; int cnt = , square = ; int T = ;
bool check(int x, int y) {
if (map[x][y] == '#' || R < x || x <= || y <= || C < y)return ;
else return ;
}
void spread(int t) {//fire at (x,y) spread.//bfs1层 while (!F.empty()) {
f v = F.front();
if (v.t == t) {
map[v.x][v.y] = '#';
F.pop();
for (int i = ; i < ; i++) {
int dx = v.x + dir[i][], dy = v.y + dir[i][];
if (check(dx, dy))continue;
map[dx][dy] = '#';
F.push(f(dx, dy, v.t + ));
}
}
else return;
}
}
void bfs(int t) {//J runs at t
while (!J.empty()) {
f v = J.front();
if (v.t == t) {
J.pop();
for (int i = ; i < ; i++) {
int dx = v.x + dir[i][], dy = v.y + dir[i][];
if (dx <= || dx > R || dy <= || dy > C) { flag = v.t + ; while (!J.empty())J.pop(); return; }
if (map[dx][dy] != '#') {
map[dx][dy] = '#';
J.push(f(dx, dy, v.t + ));
}
}
}
else return;
}
}
int main() {
int t; cin >> t;
while (t--) {
while (!J.empty())J.pop();
while (!F.empty())F.pop();
cin >> R >> C;
for (int i = ; i <= R; i++) {
scanf("%s", map[i] + );
for (int j = ; j <= C; j++)if (map[i][j] == 'F') F.push(f(i, j, )), fired[i][j] = ; else if (map[i][j] == 'J')J.push(f(i, j, )), map[i][j] = '#';
}
flag = -;
T = ;
int tf = , tj = ;
while (!J.empty()) {
spread(T);
bfs(T);
T++;
if (flag > )break;
} if (flag == -)cout << "IMPOSSIBLE" << endl;
else cout << flag << endl;
}
cin >> t;
}
同学的想法是两次bfs，先bfs一次火的，把它抵达各个格子的时间填在一个表里，说明人在这个时间之后就不能走到这里了，把这个判断加到人的bfs里面即可
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string.h> using namespace std;
char map[][];
int vis[][];
int tf[][];
int n, m, ji, jj, fi, fj;
struct Node {
int i, j;
Node(int i = , int j = ) :i(i), j(j) {}
};
queue<Node>q;
int dir[][] = { { , },{ -, },{ , },{ ,- } };
void bfsf() {
while (!q.empty()) {
Node t = q.front();
q.pop();
for (int k = ; k<; k++) {
int di = t.i + dir[k][];
int dj = t.j + dir[k][];
if (di< || di >= n || dj< || dj >= m || map[di][dj] == '#' || tf[di][dj] != -) continue;
q.push(Node(di, dj));
tf[di][dj] = tf[t.i][t.j] + ;
}
}
} int bfsj(int i, int j) {
queue<Node>que;
que.push(Node(i, j));
vis[i][j] = ;
while (!que.empty()) {
Node t = que.front();
que.pop();
if (t.i == || t.i == n - || t.j == || t.j == m - )
return vis[t.i][t.j] + ;
for (int k = ; k<; k++) {
int di = t.i + dir[k][];
int dj = t.j + dir[k][];
if (di< || di >= n || dj< || dj >= m || map[di][dj] == '#' || (vis[di][dj] != - || vis[t.i][t.j] + >= tf[di][dj]&&tf[di][dj]>)) continue;
que.push(Node(di, dj));
vis[di][dj] = vis[t.i][t.j] + ;
}
}
return -;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
memset(tf, -, sizeof(tf));
scanf("%d%d", &n, &m);
for (int i = ; i<n; i++) {
scanf("%s", map[i]);
for (int j = ; j<m; j++) {
if (map[i][j] == 'J') ji = i, jj = j;
if (map[i][j] == 'F') q.push(Node(i, j)), tf[i][j] = ;
}
}
bfsf();
/*for (int i = 0; i < n; i++) {
for (int j = 0; j <= m; j++) cout << tf[i][j] << ' '; cout << endl;
}*/ memset(vis, -, sizeof(vis));
int ans = bfsj(ji, jj);
if (ans == -) printf("IMPOSSIBLE\n");
else printf("%d\n", ans); }
return ;
}