网站建设项目分期,找人做一个网站要多少钱,wordpress 添加付款,口碑好的五屏网站建设难度#xff1a;普及-
题目背景
在峰会期间#xff0c;武装部队得处于高度戒备。警察将监视每一条大街#xff0c;军队将保卫建筑物#xff0c;领空将布满了 F-2003 飞机。
此外#xff0c;巡洋船只和舰队将被派去保护海岸线。不幸的是#xff0c;因为种种原因#x…难度普及-
题目背景
在峰会期间武装部队得处于高度戒备。警察将监视每一条大街军队将保卫建筑物领空将布满了 F-2003 飞机。
此外巡洋船只和舰队将被派去保护海岸线。不幸的是因为种种原因国防海军部仅有很少的几位军官能指挥大型海战。因此他们培养了一些新海军指挥官。军官们选择了“海战”游戏来帮助他们学习。
题目描述
在一个方形的盘上放置了固定数量和形状的船只每只船却不能碰到其它的船。在本题中我们认为船是方形的所有的船只都是由图形组成的方形。
求出该棋盘上放置的船只的总数。
输入格式
第一行为两个整数 R 和 C用空格隔开分别表示游戏棋盘的行数和列数。
接下来 R 行每行 C 个字符为 # 或 .。# 表示船只的一部分. 表示水。
输出格式
一行一个字符串如果船的位置放得正确即棋盘上只存在相互之间不能接触的方形如果两个 # 号上下相邻或左右相邻却分属两艘不同的船只则称这两艘船相互接触了。就输出 There are S ships.S 表示船只的数量。否则输出 Bad placement.。
输入输出样例
输入 #1 6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...# 输出 #1 There are 5 ships. 说明/提示
对于 100% 的数据1≤R,C≤1000。
思路
输入后找‘#’判断该‘#’所在方阵是否合法。如不合法直接输出“Bad placement.”并结束程序合法的话用染色的办法删除该方阵ans找下一个‘#’输出ans。 完整代码
#include bits/stdc.h
using namespace std;
int r,c,ans;
char sea[1010][1010];
bool pdfalse;
void dfs(int x,int y)
{int heng,shu,temp0;for(shuy;;shu) if(sea[x][shu] . || shu c) break;shu--;for(hengx;;heng) if(sea[heng][y] . || heng r) break;heng--;for(int iy;ishu;i){for(int jx;sea[j][i] #;j) temp;if(temp ! heng-x1) {printf(Bad placement.); pdtrue; return ;}temp0;}for(int ix;iheng;i){for(int jy;sea[i][j] #;j) temp;if(temp ! shu-y1) {printf(Bad placement.); pdtrue; return ;}temp0;} for(int ix;iheng;i)for(int jy;jshu;j) sea[i][j]*;ans;return ;
}
int main(){scanf(%d %d,r,c);for(int i1;ir;i)for(int j1;jc;j) cin sea[i][j];for(int i1;ir;i)for(int j1;jc;j){if(sea[i][j] #) dfs(i,j);if(pd true) return 0;}printf(There are %d ships.,ans);return 0;
}
