uva 11624 - Fire!

点击打开链接uva 11624

思路：bfs
分析：
1 题目要判断joe是否可以逃出迷宫，如果可以输出最小的时间，否则输出impossible
2 题目明确规定有且仅有一个Joe，但是火的个数是不确定的
3 那么如果没有火，我们只要去求Joe走出迷宫的时间即可。但是如果有火的话这里将碰到火在蔓延并且人在走，但是对于火来说我们可以先预处理出每一个可以着火的点的着火时间，然后在利用bfs搜索只有当前这个结点的着火时间大于人到的时间我们才加入队列
4 所以我们只需要两次的bfs即可

代码：

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;

struct Node{
    int x;
    int y;
    int t;
};
Node start;
char maze[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int timeState[MAXN][MAXN];
int n , m;
queue<Node>q;

bool ok(int x , int y){
    if(x >= 0 && x < n && y >= 0 && y < m)
        return true;
    return false;
}

//初始化并且预处理每个点的着火的时间
void init(){
    //找起始点    
    bool isFire = false;
    while(!q.empty())
        q.pop();
    memset(timeState , INF , sizeof(timeState));
    memset(vis , false , sizeof(vis));
    for(int i = 0 ; i < n ; i++){
       for(int j = 0 ; j < m ; j++){ 
          if(maze[i][j] == 'J'){ 
               start.x = i; 
               start.y = j;
               start.t = 0;
          }
          if(maze[i][j] == 'F'){
               isFire = true;
               vis[i][j] = true;
               timeState[i][j] = 0; 
               q.push((Node){i,j,0});
          }
       }
    }
    if(!isFire)
        return;
    //预处理出每一个点的着火的时间
    while(!q.empty()){
         Node tmp = q.front();
         q.pop();
         for(int i = 0 ; i < 4 ; i++){
             int tx = tmp.x + dir[i][0];
             int ty = tmp.y + dir[i][1];
             if(ok(tx , ty) && !vis[tx][ty] && maze[tx][ty] == '.'){
                vis[tx][ty] = true;
                timeState[tx][ty] = tmp.t+1;; 
                q.push((Node){tx , ty , tmp.t+1});
             }
         }
    }
}

int solve(){
    while(!q.empty())
        q.pop();
    q.push(start);
    memset(vis , false , sizeof(vis));
    vis[start.x][start.y] = true;
    //广搜
    while(!q.empty()){
         Node tmp = q.front();
         q.pop();
         //进行四个方向的遍历
         for(int i = 0 ; i < 4 ; i++){
             int tx = tmp.x + dir[i][0];
             int ty = tmp.y + dir[i][1];
             if(!ok(tx , ty))
                 return tmp.t+1;
             if(!vis[tx][ty] && maze[tx][ty] == '.' && tmp.t+1 < timeState[tx][ty]){
                 q.push((Node){tx , ty , tmp.t+1});
                 vis[tx][ty] = true;
             }
         }
    }
    return INF;
}

int main(){
    int Case;
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d%d%*c" , &n , &m); 
        for(int i = 0 ; i < n ; i++)
            gets(maze[i]);
        init();
        int ans = solve();
        if(ans != INF)
           printf("%d\n" , ans);
        else
           puts("IMPOSSIBLE");
    }
    return 0;
}