题目描述

在峰会期间，武装部队得处于高度戒备。警察将监视每一条大街，军队将保卫建筑物，领空将布满了F-2003飞机。此外，巡洋船只和舰队将被派去保护海岸线。不幸的是因为种种原因，国防海军部仅有很少的几位军官能指挥大型海战。因此，他们考虑培养一些新的海军指挥官，他们选择了“海战”游戏来帮助学习。

在这个著名的游戏中，在一个方形的盘上放置了固定数量和形状的船只，每只船却不能碰到其它的船。在这个题中，我们仅考虑船是方形的，所有的船只都是由图形组成的方形。编写程序求出该棋盘上放置的船只的总数。

输入格式

输入文件头一行由用空格隔开的两个整数R和C组成，1<=R,C<=1000，这两个数分别表示游戏棋盘的行数和列数。接下来的R行每行包含C个字符，每个字符可以为“#”，也可为“.”，“#”表示船只的一部分，“.”表示水。

输出格式

为每一个段落输出一行解。如果船的位置放得正确（即棋盘上只存在相互之间不能接触的方形，如果两个“#”号上下相邻或左右相邻却分属两艘不同的船只，则称这两艘船相互接触了）。就输出一段话“There are S ships.”,S表示船只的数量。否则输出“Bad placement.”。

输入输出样例

输入 #1

6 8 .....#.# .....# .....# .......# #......# #..#...#

输出 #1

讯享网There are 5 ships.

思路：先判断是否合法，不合法直接结束程序。如果合法就深搜找到每只船的一部分，然后用bfs将该船填充与还没搜索到的船进行区分。直到dfs完整张地图，输出船数

 #include <iostream> //#include<fstream> #include<ctime> #include<math.h> #include<string> #include<vector> #include<algorithm> #include<queue> using namespace std; int v1[] = { -1,1,0,0 }; int v2[] = { 0,0,-1,1 }; int arr[1010][1010] = { 0 }; int used1[1010][1010] = { 0 }, used2[1010][1010] = { 0 }; struct node { int x; int y; }; int sum = 0; int r, c; void bfs(int x, int y) {//用于搜索船的大小 queue<node>q; q.push({ x,y }); arr[x][y]++; while (!q.empty()) { node now = q.front(); q.pop(); for (int j = 0; j < 4; j++) { int nextx = now.x + v1[j], nexty = now.y + v2[j]; if (arr[nextx][nexty] == 1) { q.push({ nextx,nexty }); arr[nextx][nexty]++; } } } } void dfs(int x, int y) { if (x > r) { cout << "There are " << sum << " ships."; exit(0);//强行结束程序避免不必要计算 } if (arr[x][y] == 0 || arr[x][y] > 1) {// 不是船或者算过了就跳过 if (y == c) { dfs(x + 1, 1); } else dfs(x, y + 1); } else { sum++;//主函数已经处理完不合法情况，这里 //放心自加 bfs(x, y);//填充搜索到的船 if (y == c) { dfs(x + 1, 1); } else dfs(x, y + 1); } } int main() { cin >> r >> c; for (int j = 1; j <= r; j++) { for (int i = 1; i <= c; i++) { char t; cin >> t; if (t == '#') arr[j][i] = 1; } }//先预处理判断是否合法 for (int x = 1; x <= r; x++) { for (int y = 1; y <= c; y++) { if (arr[x][y] == 1) { /*有四种情况不合法 # # # # 没想到什么好方法 硬摆条件讨论 */ if ((arr[x + 1][y] > 0 && arr[x][y + 1] > 0 && arr[x + 1][y + 1] == 0) || (arr[x - 1][y] > 0 && arr[x][y - 1] > 0 && arr[x - 1][y - 1] == 0) || (arr[x][y - 1] > 0 && arr[x + 1][y] && arr[x + 1][y - 1] == 0) || (arr[x][y + 1] > 0 && arr[x - 1][y] > 0 && arr[x - 1][y + 1] == 0)) { cout << "Bad placement."; exit(0); } } } } dfs(1, 1);//深搜 return 0; }

  Lake Counting S

题目描述

Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John's field, determine how many ponds he has.

讯享网

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个NxM(1<=N<=100;1<=M<=100)网格图表示。每个网格中有水('W') 或是旱地('.')。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入格式

Line 1: Two space-separated integers: N and M * Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.

第1行：两个空格隔开的整数：N 和 M 第2行到第N+1行：每行M个字符，每个字符是'W'或'.'，它们表示网格图中的一排。字符之间没有空格。

输出格式

Line 1: The number of ponds in Farmer John's field.

一行：水坑的数量

输入输出样例

输入 #1复制

讯享网10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W. 

输出 #1复制

3 

说明/提示

OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.

思路：跟上一题思路差不多，而且更简单不用判断非法。这里采用循环的方法和上一题dfs区分（其实本质都是找到一小部分然后填充区分）

讯享网#include <iostream> #include<math.h> #include<string> #include<vector> #include<algorithm> #include<queue> #include <iomanip> #include<string> using namespace std; int n,m; int arr[102][102] = { 0 }; int used[102][102] = { 0 }; int v1[] = { 0,-1,-1,-1,0,0,1,1,1 };//x方向 int v2[] = { 0,-1,0,1,-1,1,-1,0,1 };//y方向 struct node { int x, y; }; void bfs(int x, int y) { queue<node>q; q.push({ x,y }); while (!q.empty()) { node now = q.front(); q.pop(); for (int j=0; j < 9; j++) { int nx=now.x+v1[j], ny=now.y+v2[j]; if (used[nx][ny] == 0 && arr[nx][ny] == 1) { used[nx][ny] = 1; arr[nx][ny]++; q.push({ nx,ny }); } } } } int main() { int sum = 0; cin >> n >> m; for (int j = 1; j <= n; j++) { for (int i = 1; i <= m; i++) { char t; cin >> t; if (t == 'W') arr[j][i] = 1; } } for (int j = 1; j <=n; j++) { for (int i = 1; i <= m; i++) { if (arr[j][i] == 1) { sum++;//搜到就计数，然后填充 bfs(j, i); } } } cout << sum; }