UVA - 11624 Fire!

题意：求Joe走出迷宫的最短时间，有障碍，还有向四周蔓延的火

思路：将火的位置也加进BFS里面

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 1200;

struct node{
    int x,y,f,t;    
};
int dx[] ={1,-1,0,0};
int dy[] ={0,0,1,-1};
int vis[MAXN][MAXN],n,m;
char map[MAXN][MAXN];

int check(node a){
    if (a.x >= 0 && a.x < n && a.y >= 0 && a.y < m)
        return 1;
    return 0;
}

int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%d%d",&n,&m);
        for (int i = 0; i < n; i++)
            scanf("%s",map[i]);
        queue<node> q;
        node Joe;
        memset(vis,0,sizeof(vis));
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (map[i][j] == ‘#‘)
                    vis[i][j] = 1;
                else if (map[i][j] == ‘F‘){
                    vis[i][j] = 1;
                    q.push((node){i,j,1,0});
                }
                else if (map[i][j] == ‘J‘){
                    vis[i][j] = 1;
                    Joe.x = i,Joe.y = j;
                    Joe.f = 0,Joe.t = 0;
                }
            }
        }
        q.push(Joe);
        int ans = -1;
        while (!q.empty()){
            node u,v;
            u = q.front(),q.pop();
            for (int i = 0; i < 4; i++){
                v = u;
                v.t++;
                v.x += dx[i],v.y += dy[i];
                if (check(v)){
                    if (vis[v.x][v.y])
                        continue;
                    vis[v.x][v.y] = 1;
                    q.push(v);
                }
                else if (v.f == 0){
                    ans = v.t;
                    break;
                }
            }
            if (ans != -1)
                break;
        }
        if (ans == -1)
            printf("IMPOSSIBLE\n");
        else printf("%d\n",ans);
    }
    return 0;
}

UVA - 11624 Fire!,布布扣,bubuko.com

UVA - 11624 Fire!

原文：http://blog.csdn.net/u011345136/article/details/20072617