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。

 // 生化武器.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h" #include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct Point
{
int x, y;
int time;
Point(int xx, int yy, int tt)
{
x = xx;
y = yy;
time = tt;
}
}; const int MAX = ;
int n, m, t, uncnt, fillcnt, dir[][] = { , , , -, , , -, };
char map[MAX][MAX];
queue<Point> q; int main()
{
while (cin>>n>>m>>t)
{
memset(map, '\0', sizeof(map));
uncnt = ;
fillcnt = ; for (int i = ; i < n; i++)
cin >> map[i]; for (int i = ; i < n; i++)
{
for (int j = ; j < m; j++)
{
if (map[i][j] == '*')
{
Point p(i,j,);
map[p.x][p.y] = '#';
fillcnt++;
q.push(p); }
else if (map[i][j] == '.')
{
uncnt++;
}
}
}
while (!q.empty() && t)
{
Point now = q.front();
q.pop();
//cout << "now.x:" << now.x << "\tnow.y:" << now.y << "\tnow.t:" << now.time << endl;
if (now.time > t) break;
for (int i = ; i < ; i++)
{
int nx = now.x + dir[i][];
int ny = now.y + dir[i][];
//cout << "nx:" << nx << "\tny:" << ny << "\tmap:" << map[nx][ny] << endl;
if (map[nx][ny] == '.' && nx >= && ny >= && nx < n && ny < m)
{
Point next(nx,ny,now.time+);
map[next.x][next.y] = '#';
fillcnt++;
q.push(next);
}
} }
if (uncnt == fillcnt) cout << "No" << endl;
else
{
for (int i = ; i < n; i++)
cout << map[i] << endl;
} } return ;
}

最新文章

  1. 【Infobright】infobright数据导入导出测试
  2. 【ros】Create a ROS package:package dependencies报错
  3. c#读properties文件
  4. ps 网页配图设计
  5. C++标准程序库的输入输出流(I/O Stream)复制文件(4种方法)
  6. MSSQL存储过程--CAST和CONVERT使用区别
  7. [SDOI2010]古代猪文
  8. wiringPi库的pwm配置及使用说明
  9. 启动tomcat报错com.sun.faces.config.ConfigureListener
  10. 我的代码库-Java8实现FTP与SFTP文件上传下载
  11. 【漏洞挖掘】攻击对外开放的Docker API接口
  12. 【WIN32编程】利用汇编写cs1.6辅助
  13. centos网络配置(手动设置,自动获取)的2种方法3
  14. 20155204 王昊《网络对抗技术》EXP4
  15. Mybatis if标签判断大小
  16. 【Shader】这是一篇记录随笔,我要开始学Shader了!
  17. uva 10618 Tango Tango Insurrection 解题报告
  18. 分离链接散列表C语言实现实例
  19. 爬虫验证码处理与IP处理
  20. 【Leetcode】【Medium】Subsets II

热门文章

  1. jdk 档案库(包含历史版本)
  2. JS事件委托或者事件代理原理以及实现
  3. 1-1SpringBoot简介
  4. 使用SourceTree的注意事项
  5. PyCharm底部控制台console界面开启/取消自动换行
  6. 排序--选择排序Selection Sort Java实现
  7. 用javaweb写一个注册界面,并将数据保存到后台数据库(全部完成)(课堂测试)
  8. 标准模板库中的链表(list)
  9. 第1节 storm编程:9、storm与kafka的整合
  10. SystemVerilog基本语法总结(上)