一道十分优美的搜索题，暴露了我对BFS了解的还不够。题意：Joe要逃离一个迷宫，迷宫中有地方起火了，在火开始燃烧的时候Joe也开始逃，火的蔓延方式与Joe的行动方式一样，都是1个单位时间可以往上下左右四个方向各走一格。另外，迷宫内有墙，Joe与火都无法穿墙。现在给你一个图，请问Joe能否从迷宫的边界处逃出而不被火烧到，如果能的话请输出最短的逃脱时间，不能的话输出“IMPOSSIBLE”。其中，‘F’代表火，‘J’代表Joe，‘#’代表墙。

我的解题思路：这题首先注意的就是，起火点可能不止一个，也可能没有起火点。其次是如果一个起火点被四周的墙给封闭起来了，那么这个火就相当于没有用了。为了判断Joe走到某个点时这个点是否已经起火，我们需要知道每个点起火的时间。通过对每个初始起火点进行BFS就可以知道每个点的起火时间了，最开始我是每个起火点都BFS一次，然后TLE了，后来才发现，其实可以把每个初始起火点当成一个起火点的邻节点加入队列，这样就只进行了一次BFS，从而获得了每个点起火的时间（如果有些点不会起火，那么这些点的时间就是初始化的INF）。最后从Joe的起点开始BFS一次，如果走到下一个点时那个点已经或者刚好着火了那就不能走，墙也不能走，只要走到边界就说明可以走出迷宫了。

我的解题代码：BFS

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; #define N 1001 #define INF 999999999 struct point //定义点结构体 { int x, y; //坐标 int step; //步数，相当于时间 }; int dx[] = {1, -1, 0, 0}; //方向向量 int dy[] = {0, 0, -1, 1}; //方向向量 int n, m, t; char map[N][N]; int vis[N][N]; //记录火或者人到达点花费的最少时间 point start, fire; //起点和起火处 queue 
       
         q; void Read(); //输入 void Init(); //初始化 void FireBfs(); //先进行起火处的Bfs void DataProcess(); //进行人的Bfs判断能否逃离以及最少逃离时间 int main() { scanf("%d", &t); while (t--) { Read(); Init(); DataProcess(); } return 0; } void Read() { scanf("%d %d", &n, &m); for (int i=0; i
        
         = n || ny < 0 || ny >= m) continue; //越界 if (map[nx][ny] == '#' || vis[nx][ny] <= a.step + 1) continue; //墙或者已经走过的点 b.x = nx; b.y = ny; b.step = vis[nx][ny] = a.step + 1; q.push(b); } } return; } void DataProcess() { point a, b; FireBfs(); q.push(start); //将人的起点加入队列准备Bfs while (!q.empty()) { a = q.front(); q.pop(); for (int i=0; i<4; ++i) { int nx = a.x + dx[i]; int ny = a.y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) //成功走到边界 { printf("%d\n", a.step + 1); return; } if (map[nx][ny] == '#' || vis[nx][ny] <= a.step + 1) continue; //遇到墙或者该点起火或者走过 b.x = nx; b.y = ny; b.step = vis[nx][ny] = a.step + 1; q.push(b); } } puts("IMPOSSIBLE"); return; }