【UVa】[11624]Fire! - BoilTask's Blog

问题描述

Fire!

[uva-11624] [3106306097285719] @vjudge

问题分析

题目：一个平面迷宫中有一个人，迷宫中有些点起火了，火和人每个单位时间只能向相邻的格子移动，其中有一些空间被墙壁占据，问这个人在不背或烧到的情况下，离开迷宫的最快时间。

分析：搜索。迷宫中的最短路，首先就会想到bfs；并且bfs利用队列会使状态空间按时间顺序分层。

而火的扩散过程正好符合这个时间的层次。所以我们会想到，利用两个队列，一个储存人的状态，一个储存火的状态。按照时间顺序，先更新火蔓延的节点，再扩展人能到达的节点。

通过分析，我们发现这两个队列可以合并，只须初始化的时候，按照火节点然后是人的顺序入队即可。

（节点中加入一个是否是火节点的判断，就可以两种节点按不同的细节处理）

本段分析参考博客：UVa 11624 - Fire! - 小白菜又菜

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<stdio.h>
#include<queue>
using namespace std;
char map[1200][1200];
int cnt[1200][1200];
int tmove[4]= {1,-1,0,0};
int inf=99999999;
struct node {
    int n,m;
} a[1020*1020];
int x;
int H,W;
int bfs(int n,int m) {
    queue<node>q;
    node t;
    for(int i=0; i<x; i++) {
        t.n=a[i].n,t.m=a[i].m;
        q.push(t);
    }
    t.n=n,t.m=m;
    q.push(t);
    while(!q.empty()) {
        t=q.front();
        if(map[t.n][t.m]=='F') {
            for(int i=0; i<4; i++) {
                int tn=t.n+tmove[i],tm=t.m+tmove[(i+2)%4];
                if(tn>=0&&tn<H&&tm>=0&&tm<W&&map[tn][tm]=='.') {
                    map[tn][tm]='F';
                    node temp;
                    temp.n=tn,temp.m=tm;
                    q.push(temp);
                }
            }
        } else {
            for(int i=0; i<4; i++) {
                int tn=t.n+tmove[i],tm=t.m+tmove[(i+2)%4];
                if(tn<0||tn>=H||tm<0||tm>=W)
                    return cnt[t.n][t.m];
                else if(map[tn][tm]=='.'&&cnt[tn][tm]==inf) {
                    map[tn][tm]='J';
                    cnt[tn][tm]=cnt[t.n][t.m]+1;
                    node temp;
                    temp.n=tn,temp.m=tm;
                    q.push(temp);
                }
            }
        }
        q.pop();
    }
    return -1;
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d %d",&H,&W);
        getchar();
        int mH,mW;
        x=0;
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) {
                cnt[i][j]=inf;
                map[i][j]=getchar();
                if(map[i][j]=='F')
                    a[x].n=i,a[x++].m=j;
                else if(map[i][j]=='J')
                    mH=i,mW=j;
            }
            getchar();
        }
        cnt[mH][mW]=1;
        int res=bfs(mH,mW);
        if(res==-1)
            printf("IMPOSSIBLE\n");
        else
            printf("%d\n",res);
    }
    return 0;
}

题目地址：Puzzle - UVA 227 - Virtual Judge