高达师哥的池塘-连通块计数问题

前言

这道题是在实验室选拔赛上的第一个简单题，我™没过这！！这题我写了1.5个小时，提交十次！！恼。。。

当时一直纠结我原本的做法，决定肯定是对的。。。其实还是错了，我当时直接遍历一遍直接判断，没有考虑完善漏情况了，这题的正确解析和做法是↓↓↓

题目

https://ac.nowcoder.com/acm/contest/106002/A

高达师哥有一片 N∗M 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，高达师哥想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

输入描述

第一行包含两个整数 N 和 M。接下来 N 行，每行包含 M 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。

输出描述

输出一个整数，表示池塘数目。

示例输入

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	数据范围1≤N,M≤1000

解析(IMPORTANT)

这是一个典型的连通块计数问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。我们需要遍历整个矩阵，每当找到一个未访问过的”W”，就开始一次搜索，将与之相连的所有”W”都标记为已访问，并计数加一。

代码实现

DFS

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL n, m, ans = 0;
LL a[1010][1010], used[1010][1010];
LL walk[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

void dfs(LL x, LL y) {
	for (LL i = 0; i < 8; i++) {
		LL xx = x + walk[i][0], yy = y + walk[i][1];
		if (xx < 0 || xx >= n || yy < 0 || yy >= m || a[xx][yy] == 1 || used[xx][yy] == 1) continue;
		used[xx][yy] = 1; // 标记
		dfs(xx, yy);
	}
}

int main() {
	cin >> n >> m;
	for (LL i = 0; i < n; i++) {
		for (LL j = 0; j < m; j++) {
			char t;
			cin >> t;
			if (t == '.') a[i][j] = 1;
			else if (t == 'W') a[i][j] = 2;
		}
	}

	for (LL i = 0; i < n; i++) {
		for (LL j = 0; j < m; j++) {
			if (a[i][j] == 1 || used[i][j]) continue;
			used[i][j] = 1;
			dfs(i, j);
			ans++;
		}
	}
	
	cout << ans;
	
	return 0;
}

BFS

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL n, m, ans = 0;
LL a[1010][1010], used[1010][1010];
LL walk[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

void bfs(LL x, LL y) {
	used[x][y] = 1;
	queue<pair<LL, LL> > Q;
	Q.push({x, y});
	
	while (!Q.empty()) {
		auto q = Q.front();
		Q.pop();
		LL xx = q.first, yy = q.second;
		used[xx][yy] = 1; // 标记
		for (LL i = 0; i < 8; i++) {
			LL x_next = xx + walk[i][0], y_next = yy + walk[i][1];
			if (x_next < 0 || x_next >= n || y_next < 0 || y_next >= m || a[x_next][y_next] == 1 || used[x_next][y_next] == 1) continue;
			Q.push({x_next, y_next});
		}
	}
}

int main() {
	cin >> n >> m;
	for (LL i = 0; i < n; i++) {
		for (LL j = 0; j < m; j++) {
			char t;
			cin >> t;
			if (t == '.') a[i][j] = 1;
			else if (t == 'W') a[i][j] = 2;
		}
	}

	for (LL i = 0; i < n; i++) {
		for (LL j = 0; j < m; j++) {
			if (a[i][j] == 1 || used[i][j]) continue;
			bfs(i, j);
			ans++;
		}
	}
	
	cout << ans;
	
	return 0;
}

BFS与DFS的主要区别

数据结构：
- DFS使用递归（隐式栈）
- BFS使用队列
搜索方式：
- DFS是深度优先，沿着一条路径一直探索到底
- BFS是广度优先，逐层扩展，先处理距离起点近的节点
实现细节：
- 在BFS中，我们将起点加入队列并标记为已访问
- 然后不断从队列取出节点，并将其未访问的邻居加入队列
- 直到队列为空，表示连通块已完全探索