题目链接：UVA-11624.Fire!
题目
题意
多组样例
第一行是指定地图 R 行 C 列
接下来输入一个地图，火（F）和Joe（J）同时走，问你 Joe 能不能不被火烧逃出地图。
解题思路
错误思路：
- 先让火走一遍广搜，记录一张时间表，记录火蔓延到每一个需要的时间。
- 然后 Joe 广搜走一遍，如果时间比火的短就可以走，如果超出地图就说明能走出来。
然而为什么上面这个方法是错的呢，主要问题出在两遍广搜会 时间超限 。
vj 评论区大佬的 tips：
- 火不止一个，可能有多处 F
【虽然还是可以再记录火的时候取最短时间记录即可 - 必须要同时广搜，火和 Joe 放在一个广搜里一起走，否则就会超时
【我猜测是，R、C 都是 1-1000，如果火能传播的距离很远但是用不了几步就能把Joe包围起来，那么火其他的传播都是浪费时间
所以如何才能同时广搜呢？
正确思路：
- 要使所有火和所有Joe可能的前进方向都同步进行，传统的队列很显然是不行了，于是我想到 F 和 J 都分别用两个队列来记录。
用一个“上一步”队列来记录已经走过的坐标，而可以走的“下一步”存放在另一个队列里，“上一步”队列遍历完以后，把“下一步”队列再赋值给“上一步”队列，然后清空“下一步”队列 - 火进行一次队列更新之后，再把Joe进行一次队列更新
相当于火先走一步，然后Joe再走。因为Joe必须比火走得快，同时走到一格里Joe还是会死，
所以先走火，然后Joe就直接不走那个格子 - 如果Joe的新队列为空，说明无路可走，返回 -1
如果Joe的下一步超出地图，说明Joe已经走出来了，返回他走的步数
正常代码
//
// _ _ ___ ____ ___ ____ _____
//| | | | / _ \ _ __ / ___/ _ \| _ \| ____|
//| |_| | | | | | '_ \ | | | | | | | | | _|
//| _ | | |_| | | | | | |__| |_| | |_| | |___
//|_| |_|___\___/|_| |_| \____\___/|____/|_____|
// |_____|
//
#include <iostream>
using namespace std;
typedef int hip;
#include <queue>
hip S(hip l, hip c) {return l*10000+c;}
hip R, C;
queue<hip> Fs, Js;
hip N[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
bool I(hip l, hip c) {return (l>=0&&l<R&&c>=0&&c<C);}
void CQ(queue<hip> &qqq) {
while (!qqq.empty()) qqq.pop();
}
hip bfs(vector<string> m) {
queue<hip> fp, jp;
hip l, c;
hip jt = 0;
while (!Js.empty()) {
jt += 1;
hip tp, tl, tc;
while (!Fs.empty()) {
tp = Fs.front(); Fs.pop();
tl = tp/10000;
tc = tp-tl*10000;
for (hip i=0;i<4;i++) {
l = tl+N[i][0];
c = tc+N[i][1];
if (I(l, c) && m[l][c]!='#') {
fp.push(S(l, c));
m[l][c] = '#';
}
}
}
Fs = fp; CQ(fp);
while (!Js.empty()) {
tp = Js.front(); Js.pop();
tl = tp/10000;
tc = tp-tl*10000;
for (hip i=0;i<4;i++) {
l = tl+N[i][0];
c = tc+N[i][1];
if (!I(l, c)) return jt;
if (m[l][c]=='.') {
jp.push(S(l, c));
m[l][c] = '#';
}
}
}
Js = jp; CQ(jp);
}
return -1;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
hip T; cin >> T;
while (T--) {
cin >> R >> C;
vector<string> m;
CQ(Js);
CQ(Fs);
for (hip i=0;i<R;i++) {
string s; cin >> s;
m.push_back(s);
for (hip j=0;j<C;j++) {
if (s[j] == 'J') Js.push(S(i, j)), m[i][j] = '#';
if (s[j] == 'F') Fs.push(S(i, j)), m[i][j] = '#';
}
}
hip r = bfs(m);
if (r == -1) cout << "IMPOSSIBLE" << endl;
else cout << r << endl;
}
return 0;
}