ACM-生化武器

Description
在一个封闭的房间里，gogo给大家表演了他的屁遁术，人果然一下没影了，但是他留下的“生化武器”，却以每秒1米的速度向上下左右扩散出去。为了知道自己会不会被“毒”到，你果断写了个算法计算出了“毒气”在t秒时间内可以到达的所有地方。

输入

有多组测试数据

第一行输入n,m,t（0<n,m<=30）

n和m表示图的行和列，t表示时间，‘*’为表演的地点，‘X’是墙，‘.’为空白的地方

输出

如果在t秒时间内毒气没有充满房间或刚好充满，输出现在房间里的情况，‘#’表示有‘毒气’的地方

否则，输出“No”

每组数据输出后有一个空行

输入样例

9 9 4

XXXXXXXXX
X...X...X
X.*.....X
X...X...X
XXXXXXXXX
X.......X
X.......X
X.......X
XXXXXXXXX

5 5 2
XXXXX
X...X
X.*.X
X...X
XXXXX

样例输出

XXXXXXXXX
X###X#..X
X######.X
X###X#..X
XXXXXXXXX
X...X
X...X
X...X
XXXXXXXXX

XXXXX
X###X
X###X
X###X
XXXXX

思路

这种题就是纯遍历，用DFS和BFS都可以，这里为了练习BFS，就是用了BFS。

 1 // 生化武器.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 
 6 #include <iostream>
 7 #include <cstring>
 8 #include <queue>
 9 using namespace std;
10 struct Point
11 {
12     int x, y;
13     int time;
14     Point(int xx, int yy, int tt)
15     {
16         x = xx;
17         y = yy;
18         time = tt;
19     }
20 };
21 
22 const int MAX = 100;
23 int n, m, t, uncnt, fillcnt, dir[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
24 char map[MAX][MAX];
25 queue<Point> q;
26 
27 
28 
29 int main()
30 {
31     while (cin>>n>>m>>t)
32     {
33         memset(map, '', sizeof(map));
34         uncnt = 0;
35         fillcnt = 0;
36 
37         for (int i = 0; i < n; i++)
38             cin >> map[i];
39                 
40         for (int i = 0; i < n; i++)
41         {
42             for (int j = 0; j < m; j++)
43             {
44                 if (map[i][j] == '*')
45                 {
46                     Point p(i,j,0);
47                     map[p.x][p.y] = '#';
48                     fillcnt++;
49                     q.push(p);    
50 
51                 }
52                 else if (map[i][j] == '.')
53                 {
54                     uncnt++;
55                 }
56             }
57         }
58         while (!q.empty() && t)
59         {
60             Point now = q.front();            
61             q.pop();
62             //cout << "now.x:" << now.x << "	now.y:" << now.y << "	now.t:" << now.time << endl;
63             if (now.time > t) break;
64             for (int i = 0; i < 4; i++)
65             {
66                 int nx = now.x + dir[i][0];
67                 int ny = now.y + dir[i][1];        
68                 //cout << "nx:" << nx << "	ny:" << ny << "	map:" << map[nx][ny] << endl;
69                 if (map[nx][ny] == '.' && nx >= 0 && ny >= 0 && nx < n && ny < m)
70                 {
71                     Point next(nx,ny,now.time+1);
72                     map[next.x][next.y] = '#';
73                     fillcnt++;
74                     q.push(next);
75                 }
76             }        
77 
78         }
79         if (uncnt == fillcnt) cout << "No" << endl;
80         else
81         {
82             for (int i = 0; i < n; i++)
83                 cout << map[i] << endl;
84         }
85 
86     }
87 
88     return 0;
89 }