题目链接：https://vjudge.net/problem/UVA-11624 题意：有一片区域，J代表人，F代表火，#代表墙，.代表空地，每秒钟火会像四周空地扩散，人每秒也只能向四周移动一格，现问你人能在不被火烧到的情况下逃出这片区域吗，如果能输出最短的时间，如果不能输出IMPOSSIBLE 解析：其实很容易想到bfs，但是题目坑点略多，调bug+看题花了很多时间，最容易想到的思路应该就是先对火bfs一遍，然后记录，每个格子几秒后会着火，然后在对人bfs，判断人是否能到边界
坑点： 1、首先初始化问题，所有格子一开始的着火时间应该是无穷大， 2、有多团火，题目说的是fires 3、队列清空
#include <bits/stdc++.h> using namespace std; const int maxn = 1005; const int inf = 0x3f3f3f3f; struct node { int x,y,step; node() {} node(int _x,int _y,int _step) { x = _x; y = _y; step = _step; } }; int n,m; char a[maxn][maxn]; int vis[maxn][maxn]; int step[maxn][maxn]; int dx[] = {0,-1,1,0}; int dy[] = {1,0,0,-1}; queue<node>q; void init() { while(!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); memset(step,inf,sizeof(step)); } void bfsf() { while(!q.empty()) { node now = q.front(); q.pop(); for(int i=0;i<4;i++) { int tx = now.x+dx[i]; int ty = now.y+dy[i]; if(tx<0 || tx>=n || ty<0 || ty>=m) continue; if(vis[tx][ty] || a[tx][ty]=='#') continue; vis[tx][ty] = 1; step[tx][ty] = now.step+1; q.push(node(tx,ty,now.step+1)); } } } int bfs(int x,int y) { memset(vis,0,sizeof(vis)); q.push(node(x,y,0)); vis[x][y] = 1; while(!q.empty()) { node now = q.front(); q.pop(); if(now.x==0 || now.y==0 || now.x==n-1 || now.y==m-1) return now.step+1; for(int i=0;i<4;i++) { int tx = now.x+dx[i]; int ty = now.y+dy[i]; if(tx<0 || tx>=n || ty<0 || ty>=m) continue; if(vis[tx][ty] || a[tx][ty]=='#') continue; if(now.step+1<step[tx][ty]) { vis[tx][ty] = 1; q.push(node(tx,ty,now.step+1)); } } } return -1; } int main(void) { int t; scanf("%d",&t); while(t--) { init(); scanf("%d %d",&n,&m); int x1,y1; for(int i=0;i<n;i++) { scanf("%s",a[i]); for(int j=0;j<m;j++) { if(a[i][j]=='J') x1 = i,y1 = j; if(a[i][j]=='F') { q.push(node(i,j,0)); vis[i][j] = 1; step[i][j] = 0; } } } bfsf(); int ans = bfs(x1,y1); if(ans==-1) puts("IMPOSSIBLE"); else printf("%d\n",ans); } return 0; } /* 2 5 5 ..... .J### ..#F# ..### ##### 3 3 FFF FJF FFF */