P1596 [USACO10OCT] 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.

输入格式

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.

输出格式

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

题意翻译

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

输入第 1 行：两个空格隔开的整数：N 和 M。

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

输出一行，表示水坑的数量。

输入输出样例

输入 #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复制

递归dfs版

#include<iostream>
#include<cstring>
#include<algorithm>#define x first
#define y second
using namespace std;typedef pair<int,int> PII;int n, m; // 定义地图的行数和列数
const int N = 110, M = N * N; // 定义常量N和M，用于数组大小
char ans[N][N]; // 存储地图信息
PII q[M]; // 队列，用于广度优先搜索
bool ret[N][N]; // 记录每个位置是否已经被访问过
int num = 0; // 记录岛屿的数量// 定义八个方向的移动向量
int a[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int b[] = {0, 1, 1, 1, 0, -1, -1, -1};// 广度优先搜索函数
void bfs(int i, int j) {ret[i][j] = true; // 标记当前位置为已访问for (int k = 0; k < 8; k++) {int x = i + a[k]; // 计算新位置的行坐标int y = j + b[k]; // 计算新位置的列坐标if (x >= 0 && x < n && y >= 0 && y < m && !ret[x][y] && ans[i][j] == 'W') {bfs(x, y); // 对新位置进行递归调用bfs}}
}int main() {scanf("%d %d", &n, &m); // 输入地图的行数和列数for (int i = 0; i < n; i++) scanf("%s", ans[i]); // 输入地图每一行的信息for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (ans[i][j] == 'W' && !ret[i][j]) { // 如果是未访问过的陆地bfs(i, j); // 调用bfs函数进行深度优先搜索num++; // 岛屿数量加一}}}cout << num << endl; // 输出岛屿的数量return 0;
}

bfs不会爆栈

#include<iostream>
#include<cstring>
#include<algorithm>#define x first
#define y second
using namespace std;typedef pair<int,int> PII;int n, m; // 定义地图的行数和列数
const int N = 110, M = N * N; // 定义常量N和M，用于数组大小
char ans[N][N]; // 存储地图信息
PII q[M]; // 队列，用于广度优先搜索
bool ret[N][N]; // 记录每个位置是否已经被访问过
int num = 0; // 记录岛屿的数量// 定义八个方向的移动向量
int a[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int b[] = {0, 1, 1, 1, 0, -1, -1, -1};// 广度优先搜索函数
void bfs(int i, int j) {ret[i][j] = true; // 标记当前位置为已访问int hh = 0, tt = 0;q[tt++] = {i, j}; // 将起始位置加入队列while (hh < tt) {PII t = q[hh++]; // 取出队首元素for (int k = 0; k < 8; k++) {int x = t.x + a[k]; // 计算新位置的行坐标int y = t.y + b[k]; // 计算新位置的列坐标if (x >= 0 && x < n && y >= 0 && y < m && !ret[x][y] && ans[x][y] == 'W') {q[tt++] = {x, y}; // 将新位置加入队列ret[x][y] = true; // 标记新位置为已访问}}}
}int main() {scanf("%d %d", &n, &m); // 输入地图的行数和列数for (int i = 0; i < n; i++) scanf("%s", ans[i]); // 输入地图每一行的信息for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (ans[i][j] == 'W' && !ret[i][j]) { // 如果是未访问过的陆地bfs(i, j); // 调用bfs函数进行广度优先搜索num++; // 岛屿数量加一}}}cout << num << endl; // 输出岛屿的数量return 0;
}