题意：J为人的位置，F（可能有多个）为火源，每1s火源都在往四周扩散，人每秒走一步，求最少走几步到地图边缘，若不能输出IMPOSSIBLE。
思路：先BFS求出火到达每个点的时间，再BFS求出人逃离的时间。
# include# include # include using namespace std;int n, m;char map[1001][1001];int fire[1001][1001], vis[1001][1001], inext[4][2] = { {1,0},{-1,0},{0,1},{0,-1}};struct node{ int x, y, step;};queue Q;void setMan(int x, int y, int t){ while(!Q.empty()) Q.pop(); int flag = 0; memset(vis, 0, sizeof(vis)); node tmp; tmp.x = x; tmp.y = y; tmp.step = t; vis[x][y] = 1; Q.push(tmp); while(!Q.empty()) { for(int i=0; i<4; ++i) { if(Q.front().x==0||Q.front().x==n-1 || Q.front().y==0 || Q.front().y==m-1) { flag = 1; break; } int mx = Q.front().x + inext[i][0]; int my = Q.front().y + inext[i][1]; if(mx<0||my<0||mx>=n||my>=m||vis[mx][my] || map[mx][my]=='#') continue; vis[mx][my] = 1; if(fire[mx][my] != -1 && Q.front().step+1 >= fire[mx][my]) continue; tmp.x = mx; tmp.y = my; tmp.step = Q.front().step + 1; Q.push(tmp); } if(flag) break; Q.pop(); } if(flag) printf("%d\n",Q.front().step+1); else puts("IMPOSSIBLE");}void setFire(){ node tmp; while(!Q.empty()) { for(int i=0; i<4; ++i) { int mx = Q.front().x + inext[i][0]; int my = Q.front().y + inext[i][1]; if(mx<0 || my<0 || mx>=n || my>=m || map[mx][my]=='#') continue; if(fire[mx][my]!=-1) continue; fire[mx][my] = Q.front().step+1; tmp.x = mx; tmp.y = my; tmp.step = Q.front().step + 1; Q.push(tmp); } Q.pop(); }}int main(){ int t, sx, sy; node tmp; scanf("%d",&t); while(t--) { while(!Q.empty()) Q.pop(); memset(fire, -1, sizeof(fire)); memset(vis, 0, sizeof(vis)); scanf("%d%d",&n,&m); for(int i=0; i