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