【题目来源】
洛谷：[P1596 USACO10OCT] Lake Counting S - 洛谷
【题目描述】
由于最近的降雨，水在农夫约翰的田地里积聚了。田地可以表示为一个 \(N \times M\) 的矩形（\(1 \leq N \leq 100\)；\(1 \leq M \leq 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.
【输出样例】
3
【解题思路】
【算法标签】
《洛谷 P1596 Lake Counting》 #搜索# #深度优先搜索,DFS# #USACO# #2010#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
int n, m, ans=0, vis[105][105]={0};
int dx[8]={-1,-1,-1,0,0,1,1,1}, dy[8]={-1,0,1,-1,1,-1,0,1}; // 定义8个方向的偏移坐标
char a[105][105];
struct node {int x, y;
};
int main()
{cin >> n >> m; // 输入n和mfor (int i=1; i<=n; i++) { // 双重for循环遍历矩阵for (int j=1; j<=m; j++) {cin >> a[i][j]; // 输入每个位置的字符，W或.}}for (int i=1; i<=n; i++) { // 双重for循环遍历矩阵for (int j=1; j<=m; j++) {if (a[i][j]=='W' && vis[i][j]==0) { // 当遇到水坑'W'，且没有访问过时ans++; // 水坑数量自增1queue<node> q; // 定义队列node tp = {i, j}; // 定义tp节点，此处用结构体来记录x和y坐标q.push(tp); // 压入队列中vis[i][j]=1; // 并标记该位置已来过while (!q.empty()) { // 当队列不为空node tp = q.front(); // 取出队头q.pop();for (int k=0; k<8; k++) { // 遍历8个方向int xx = tp.x + dx[k]; // 得到移动后的x坐标int yy = tp.y + dy[k]; // 得到移动后的y坐标if (xx<1 || yy<1) continue; // 进行边界判断，超边界的继续循环if (a[xx][yy]=='W' && vis[xx][yy]==0) { // 如果移动后仍为水坑'W'，且没有访问过node t = {xx,yy}; // 定义tq.push(t); // 将t压入队列中vis[xx][yy]=1; // 并标记该位置已来过}}} }}}cout << ans << endl; // 最后输出水坑数量return 0;
}
【运行结果】
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
3