题目描述
在峰会期间,武装部队得处于高度戒备。警察将监视每一条大街,军队将保卫建筑物,领空将布满了F-2003飞机。此外,巡洋船只和舰队将被派去保护海岸线。不幸的是因为种种原因,国防海军部仅有很少的几位军官能指挥大型海战。因此,他们考虑培养一些新的海军指挥官,他们选择了“海战”游戏来帮助学习。
在这个著名的游戏中,在一个方形的盘上放置了固定数量和形状的船只,每只船却不能碰到其它的船。在这个题中,我们仅考虑船是方形的,所有的船只都是由图形组成的方形。编写程序求出该棋盘上放置的船只的总数。
输入输出格式
输入格式:
输入文件头一行由用空格隔开的两个整数R和C组成,1<=R,C<=1000,这两个数分别表示游戏棋盘的行数和列数。接下来的R行每行包含C个字符,每个字符可以为“#”,也可为“.”,“#”表示船只的一部分,“.”表示水。
输出格式:
为每一个段落输出一行解。如果船的位置放得正确(即棋盘上只存在相互之间不能接触的方形,如果两个“#”号上下相邻或左右相邻却分属两艘不同的船只,则称这两艘船相互接触了)。就输出一段话“There are S ships.”,S表示船只的数量。否则输出“Bad placement.”。
输入输出样例
6 8 .....#.# ##.....# ##.....# .......# #......# #..#...# 输出样例#1:
There are 5 ships. 【思路】:一看题,这TM不就是标准的dfs吗?问题应该就是在怎么判断两艘船是不是撞了。其实也不是太难。
..... .###. .###. ..... 这样可以理解为一条船 一旦装船了 ..... .A#.. .##.. ..... 则必定会形成一个非矩形的形状所以要判断2x2的格子里#的数量
献上代码:
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; ]= {,-,,}; ]= {-,,,}; int r,c; ][]; int judge(int i,int j) { ; if(a[i][j]=='#') js++; ][j]=='#') js++; ]=='#') js++; ][j+]=='#') js++; ); ; } int dfs(int x,int y) { a[x][y]='*'; ; i<; ++i) { &&y+dy[i]<=c&&y+dy[i]>) { dfs(x+dx[i],y+dy[i]); } } } int main() { cin>>r>>c; ; i<=r; ++i) { ; j<=c; ++j) { cin>>a[i][j]; } } ; i<=r; ++i) { ; j<=c; ++j) { if(i<r&&j<c&&!judge(i,j)) { cout<<"Bad placement.\n"; ; } } } ; ; i<=r; ++i) { ; j<=c; ++j) { if(a[i][j]=='#') { calc++; dfs(i,j); } } } cout<<"There are "<<calc<<" ships."; ; }
【dfs】P1331 海战的更多相关文章
-
P1331 海战
P1331 海战 题目描述 在峰会期间,武装部队得处于高度戒备.警察将监视每一条大街,军队将保卫建筑物,领空将布满了F-2003飞机.此外,巡洋船只和舰队将被派去保护海岸线.不幸的是因为种种原因,国防 ...
-
洛谷——P1331 海战
P1331 海战 题目描述 在峰会期间,武装部队得处于高度戒备.警察将监视每一条大街,军队将保卫建筑物,领空将布满了F-2003飞机.此外,巡洋船只和舰队将被派去保护海岸线.不幸的是因为种种原因,国防 ...
-
P1331 海战 洛谷
题目描述 在峰会期间,武装部队得处于高度戒备.警察将监视每一条大街,军队将保卫建筑物,领空将布满了F-2003飞机.此外,巡洋船只和舰队将被派去保护海岸线.不幸的是因为种种原因,国防海军部仅有很少的几 ...
-
洛谷P1331 海战 题解
题目传送门 思路 肯定食用dfs啦... 但关键是两条船接触了怎么判断呢?? 上图: 可以发现一下规律 当两条船接触时,必有一条直线连续穿过两条船 当一条船不与另一条船接触时,没有一条直线连续穿过两条 ...
-
洛谷P1331 海战
海战 题目链接 这还是一道联通块的题,只是需要判断是否存在以下四种情况: o. .o oo oo oo oo o. .o 如果存在就是Bad placement. 要注意标记以下,不然会出现多次输出B ...
-
洛谷P1331海战
题目描述 在峰会期间,武装部队得处于高度戒备.警察将监视每一条大街,军队将保卫建筑物,领空将布满了F-2003飞机.此外,巡洋船只和舰队将被派去保护海岸线. 不幸的是因为种种原因,国防海军部仅有很少的 ...
-
洛谷 P1331 海战
传送门 题解:由于船是方形的,所以比较简单.但是考试的时候跪了,orz.忘了考虑类似一圈井号中间有一摊水. 可以只考虑这个点上方和左边点的情况,这样分为四种情况.一种是左边是一滩水, ...
-
海战(洛谷 P1331)
题目描述 在峰会期间,武装部队得处于高度戒备.警察将监视每一条大街,军队将保卫建筑物,领空将布满了F-2003飞机.此外,巡洋船只和舰队将被派去保护海岸线.不幸的是因为种种原因,国防海军部仅有很少的几 ...
-
nyoj 1237 最大岛屿(dfs)
描述 神秘的海洋,惊险的探险之路,打捞海底宝藏,激烈的海战,海盗劫富等等.加勒比海盗,你知道吧?杰克船长驾驶着自己的的战船黑珍珠1号要征服各个海岛的海盜,最后成为海盗王. 这是一个由海洋.岛屿和海盗组 ...
随机推荐
-
Threejs中的材质贴图
最近项目需要折腾three.js,有关three.js几点说明 1.作用 threejs适合创建简单的模型视图 2.对于复杂的模型图(如:室内模型图)需要美术3D制作,前端导成特定格式文件(如*.mt ...
-
【JVM】JVM系列之内存模型(六)
一.前言 经过前面的学习,我们终于进入了虚拟机最后一部分的学习,内存模型.理解内存模型对我们理解虚拟机.正确使用多线程编程提供很大帮助.下面开始正式学习. 二.Java并发基础 在并发编程中存在两个关 ...
-
linux特殊权限SUID、SGID、SBIT
对于linux中文件或目录的权限,应该都知道普通的rwx权限(关于linux中rwx权限的看我的这篇博文http://www.cnblogs.com/javaee6/p/3994750.html).我 ...
-
C++系统预定义4个用于标准数据流对象
C++系统预定义4个用于标准数据流对象 cin cout cerr clog C++里关于cerr,clog,cout三者的区别: cerr(无缓冲标准错误)-----没有缓冲,发送给它的 ...
-
【JavaScript】Html form 提交表单方式
源:http://blog.csdn.net/wang02011/article/details/6299517 1.input[type='submit'] 2.input[type='image' ...
-
z-index 详解
Definition and Usage The z-index property specifies the stack order of an element. An element with g ...
-
TODO Auto-generated method stub
在 菜单栏中 Window --> Preferences -->Java -->Code Style -->Code Templates--> Code --> ...
-
[node.js] fs.renameSync()报错
初学node.js,跟着node入门,操作了一遍.在最后一步,上传图片并显示时遇到报错 fs.js: throw err; ^ Error: ENOENT: no such file or direc ...
-
NodeJs安装以及注意事项
1.测试NodeJs是否安装成功 node --version npm -v 配置node的可执行文件路径到环境变量path 2.安装相关环境 npm install express -g npm i ...
-
hive表信息查询:查看表结构、表操作等--转
原文地址:http://www.aboutyun.com/forum.PHP?mod=viewthread&tid=8590&highlight=Hive 问题导读:1.如何查看hiv ...