【算法】UVa 11624, Fire! 解题心得

题目大意：

在迷宫中，有一个位置是起始位置，可能有一个或多个位置是着火点，火势与人一样每次前进一格（上下左右）。
输入: 迷宫
输出: 走出迷宫的最少步数，不能则输出“IMPOSSIBLE”。

思路：

从题目中很容易分辨出这是一个搜索问题，可以使用dfs、bfs。而使用dfs必然需要得出所有抵达出口的火/人的时间点，这种方法对于题目来说运行时间过长，故还是需要使用bfs。下面介绍一下bfs使用的具体方法：
1. 为了方便，我将所有的点都放在了同一个list中，由于在进行bfs时，我只需要取出结尾的值，或者在首部添加位置，使用list效率会更高；
2. 可以将两者放入同一个list中的支持条件：在bfs的过程中，无论是人或火走过的路都不需要再走，因为即便火将人走过的路覆盖，此时也落在人的后面，通过这个位置不可能再追上，且不能走回头路；
3. 在list中保存的值包含了当前的坐标x, y，以及flag用来标记存入的是人的位置还是火的位置--因为将人和火一起存放了，且需要注意，人的位置总是在火的前方，如此，两者同时到达的情况下，人是不可走的；
4. 在搜索过程中，搜索结束条件有两个：
　　(1) list中没有人的标签了，说明已经走到了死路，即不可达；
　　(2) 人的标签出现在出口。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <list>
  4 
  5 using namespace std;
  6 
  7 #define MAXN 1010
  8 struct Point{
  9     int x;
 10     int y;
 11     int flag; // 判断是火还是人 
 12 };
 13 
 14 /**
 15 *    走过或被火蔓延的都不能再次走 
 16 **/
 17 
 18 char ori[MAXN][MAXN];
 19 bool vis[MAXN][MAXN];
 20 
 21 list<Point> allL;
 22 int R, C;
 23 
 24 bool helper(int x, int y){
 25     return x>=0 && x<R && y>=0 && y<C && vis[x][y];
 26 }
 27 
 28 bool helper2(int x, int y){
 29     return (x==0 || x==R-1 || y==0 || y==C-1) && vis[x][y];
 30 }
 31 
 32 int bfs(){
 33     int count = 0;    // 直接返回count+1 
 34     int listSize;
 35     bool ownFlag = true;    // 当前是否还存在可走的路 
 36     while(ownFlag){
 37         ownFlag = false;
 38         count++;    // 设置已经走了一步 
 39         listSize = allL.size(); 
 40         int tempX, tempY;
 41         while(listSize--){
 42             Point curP = allL.back();
 43             allL.pop_back();
 44             tempX = curP.x;
 45             tempY = curP.y;
 46             
 47             if(curP.flag){
 48                 ownFlag = true;
 49                 if(helper2(tempX-1, tempY) || helper2(tempX+1, tempY) 
 50                          ||  helper2(tempX, tempY-1) || helper2(tempX, tempY+1))
 51                          return count+1;
 52             }    
 53             
 54             // 火势蔓延 
 55             if(helper(tempX-1, tempY)){
 56                 vis[tempX-1][tempY] = 0;
 57                 allL.push_front({tempX-1, tempY, curP.flag});
 58             }
 59             if(helper(tempX+1, tempY)){
 60                 vis[tempX+1][tempY] = 0;
 61                 allL.push_front({tempX+1, tempY, curP.flag});
 62             }
 63             if(helper(tempX, tempY-1)){
 64                 vis[tempX][tempY-1] = 0;
 65                 allL.push_front({tempX, tempY-1, curP.flag});
 66             }
 67             if(helper(tempX, tempY+1)){
 68                 vis[tempX][tempY+1] = 0;
 69                 allL.push_front({tempX, tempY+1, curP.flag});
 70             }
 71         }
 72     }
 73     
 74     return -1;
 75 }
 76 
 77 
 78 int main(){
 79     int T;
 80     scanf("%d", &T);
 81     while(T--){
 82         scanf("%d %d", &R, &C);
 83         allL.clear();
 84         
 85         int staX, staY;
 86         for(int i=0; i<R; i++)
 87             for(int j=0; j<C; j++){
 88                 cin >> ori[i][j];
 89                 vis[i][j] = 1;
 90                 if(ori[i][j] != '.')
 91                     vis[i][j] = 0;
 92                 if(ori[i][j] == 'F')
 93                     allL.push_front({i, j, 0});
 94                 else if(ori[i][j] == 'J')
 95                     staX = i, staY = j;
 96             }
 97         
 98         allL.push_front({staX, staY, 1});
 99             
100         if(staX==0 || staX==R-1 || staY==0 || staY==C-1)
101             printf("1
");
102         
103         else{
104             int res = bfs();
105             res==-1 ? printf("IMPOSSIBLE
") : printf("%d
", res);
106         }
107     }
108     
109     return 0;
110 }

UVa 11624