UVa 11624 (BFS) Fire!

也是一个走迷宫的问题，不过又有了点变化。

这里迷宫里有若干把火，而且火每秒也是向四个方向蔓延的。问人是否能走出迷宫。

我用了两遍BFS，第一遍把所有着火的格子加入队列，然后计算每个格子着火的时间。

第二遍便是走迷宫，只有当这个格子不是墙，而且当前时间在这个格子着火之前才能拓展。当然，并不是所有的空格都一定会着火。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 
 6 struct Node
 7 {
 8     int x, y, t;
 9     Node(int x=0, int y=0, int t=0):x(x), y(y), t(t) {}
10 };
11 
12 Node st;
13 
14 const int maxn = 1000 + 10;
15 int row, col;
16 char maze[maxn][maxn];
17 int time[maxn][maxn];
18 bool vis[maxn][maxn];
19 
20 int dx[] = { 0, 1, 0, -1 };
21 int dy[] = { 1, 0, -1, 0 };
22 
23 inline bool in(int x, int y)
24 { return x >= 0 && x < row && y >= 0 && y < col; }
25 
26 inline bool border(int x, int y)
27 { return x == 0 || x == row-1 || y == 0 || y == col-1; }
28 
29 void init()
30 {
31     memset(time, -1, sizeof(time));
32     queue<Node> Q;
33     for(int i = 0; i < row; i++)
34         for(int j = 0; j < col; j++)
35         {
36             if(maze[i][j] == 'F') { Q.push(Node(i, j, 0)); time[i][j] = 0; }
37             if(maze[i][j] == 'J') { st.x = i; st.y = j; st.t = 0; }
38         }
39     while(!Q.empty())
40     {
41         Node now = Q.front(); Q.pop();
42         for(int i = 0; i < 4; i++)
43         {
44             int x = now.x + dx[i];
45             int y = now.y + dy[i];
46             int t = now.t + 1;
47             if(in(x, y) && time[x][y] < 0 && maze[x][y] != '#')
48             {
49                 Q.push(Node(x, y, now.t + 1));
50                 time[x][y] = t;
51             }
52         }
53     }
54 }
55 
56 int BFS()
57 {
58     memset(vis, false, sizeof(vis));
59     queue<Node> Q;
60     Q.push(st);
61     vis[st.x][st.y] = true;
62     while(!Q.empty())
63     {
64         Node now = Q.front(); Q.pop();
65         if(border(now.x, now.y)) return now.t + 1;
66         for(int i = 0; i < 4; i++)
67         {
68             int x = now.x + dx[i];
69             int y = now.y + dy[i];
70             int t = now.t + 1;
71             if(in(x, y) && !vis[x][y] && maze[x][y] != '#')
72             {
73                 if(time[x][y] >= 0 && time[x][y] <= t) continue;
74                 vis[x][y] = true;
75                 Q.push(Node(x, y, t));
76             }
77         }
78     }
79     return 0;
80 }
81 
82 int main()
83 {
84     //freopen("in.txt", "r", stdin);
85 
86     int T; scanf("%d", &T);
87     while(T--)
88     {
89         scanf("%d%d", &row, &col);
90         for(int i = 0; i < row; i++) scanf("%s", maze[i]);
91         init();
92         int ans = BFS();
93         if(ans) printf("%d
", ans);
94         else puts("IMPOSSIBLE");
95     }
96 
97     return 0;
98 }

代码君