当前位置：首页 > news >正文

AcWing 1097池塘计数题解：手把手教你用BFS/DFS搞定Flood Fill（附C++代码调试技巧）

news 2026/4/19 14:29:19

Flood Fill算法实战：从八连通池塘计数到竞赛代码优化

遇到矩阵中的连通块计数问题，很多初学者会感到无从下手。Flood Fill算法正是解决这类问题的利器，它像油漆桶工具一样扩散填充，帮助我们快速统计连通区域。今天我们就以AcWing 1097池塘计数为例，深入探讨如何用BFS和DFS两种方式实现八连通填充，并分享几个提升竞赛代码效率的实用技巧。

1. 理解Flood Fill与八连通问题

Flood Fill算法源于图像处理中的填充操作，核心思想是从一个种子点出发，向四周扩散标记所有连通的相似点。在算法竞赛中，它常被用于解决矩阵中的连通区域问题。

八连通指的是每个单元格与周围八个方向（上、下、左、右及四个对角线方向）相邻的单元格相连。这与四连通（仅上下左右）形成对比，在处理对角线连接的情况时更为全面。

考虑以下池塘分布示例：

W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.

这里需要识别出独立的"W"区域，统计池塘数量。正确的输出应该是3，表示有3个互不连通的积水区域。

2. BFS实现与细节处理

广度优先搜索(BFS)是实现Flood Fill的经典方法，特别适合大规模网格的遍历。下面是BFS实现的完整代码框架：

#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 5; char grid[N][N]; int n, m, count = 0; // 八方向移动数组 int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; void bfs(int x, int y) { queue<pair<int, int>> q; q.push({x, y}); grid[x][y] = '.'; // 标记为已访问 while (!q.empty()) { auto [cx, cy] = q.front(); q.pop(); for (int i = 0; i < 8; i++) { int nx = cx + dx[i]; int ny = cy + dy[i]; // 边界检查 if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 'W') { grid[nx][ny] = '.'; q.push({nx, ny}); } } } } int main() { cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> grid[i][j]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 'W') { bfs(i, j); count++; } } } cout << count << endl; return 0; }

几个关键优化点：

使用pair替代结构体：减少代码量，提高可读性
边界检查前置：在访问数组元素前先验证索引有效性
原地标记：直接修改原数组，节省额外空间

注意：当网格非常大时(如1000x1000)，BFS的队列实现方式会影响性能。使用STL queue可能不如手写循环队列高效。

3. DFS实现与递归优化

深度优先搜索(DFS)提供了另一种实现思路，代码更为简洁：

void dfs(int x, int y) { grid[x][y] = '.'; for (int i = 0; i < 8; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 'W') { dfs(nx, ny); } } }

虽然DFS代码更短，但在实际应用中需要注意：

递归深度限制：对于大网格可能导致栈溢出
性能差异：DFS通常比BFS稍慢，因为递归调用有额外开销

对于竞赛编程，当网格规模不大时(如n,m≤300)，DFS是更简洁的选择。但在面对极限数据时，BFS更为可靠。

4. 调试技巧与常见错误

在实现Flood Fill算法时，有几个常见陷阱需要注意：

边界条件处理不当：
- 忘记检查数组越界
- 错误计算行列范围
标记方式选择：
- 使用额外vis数组 vs 原地修改
- 标记时机不正确导致重复访问
方向数组定义错误：
- 八连通方向遗漏或重复
- dx和dy数组不匹配

调试时可以采用的策略：

小规模测试：先用题目给的样例测试
边界测试：构造全W或全.的极端情况
打印中间状态：输出遍历过程中的网格状态

// 调试打印函数示例 void printGrid() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cerr << grid[i][j]; } cerr << endl; } cerr << "----------" << endl; }

5. 性能分析与优化

对于N×M的网格，两种算法的时间复杂度都是O(N×M)，因为每个单元格最多被访问一次。但实际运行时间可能因实现方式不同而有显著差异。

性能对比表：

实现方式	时间复杂度	空间复杂度	适用场景
BFS+队列	O(N×M)	O(N×M)	大规模网格，需要层级信息
DFS递归	O(N×M)	O(N×M)	小规模网格，代码简洁优先
DFS栈模拟	O(N×M)	O(N×M)	避免递归深度问题

几个优化方向：

输入输出加速：

ios::sync_with_stdio(false); cin.tie(0);

减少分支预测失败：

// 将条件判断改为位运算 if ((unsigned)tx < n && (unsigned)ty < m && grid[tx][ty] == 'W')

循环展开：

// 手动展开八方向循环 if (x > 0 && grid[x-1][y] == 'W') dfs(x-1, y); if (x > 0 && y < m-1 && grid[x-1][y+1] == 'W') dfs(x-1, y+1); // ...其他六个方向

6. 扩展应用与变种

Flood Fill算法不仅限于池塘计数，还有许多变种和应用场景：

统计连通块属性：
- 最大连通块面积
- 连通块形状特征
双连通分量：
- 寻找必须经过的关节点
- 网络可靠性分析
带权连通问题：
- 考虑单元格的不同权重
- 最短路径变种

例如，计算最大池塘面积的修改版BFS：

int bfs_area(int x, int y) { int area = 0; queue<pair<int, int>> q; q.push({x, y}); grid[x][y] = '.'; while (!q.empty()) { auto [cx, cy] = q.front(); q.pop(); area++; for (int i = 0; i < 8; i++) { int nx = cx + dx[i]; int ny = cy + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 'W') { grid[nx][ny] = '.'; q.push({nx, ny}); } } } return area; }

在竞赛中遇到Flood Fill类题目时，建议先明确几个关键点：