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

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) { queuepairint, 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][y1] W) dfs(x-1, y1); // ...其他六个方向6. 扩展应用与变种Flood Fill算法不仅限于池塘计数还有许多变种和应用场景统计连通块属性最大连通块面积连通块形状特征双连通分量寻找必须经过的关节点网络可靠性分析带权连通问题考虑单元格的不同权重最短路径变种例如计算最大池塘面积的修改版BFSint bfs_area(int x, int y) { int area 0; queuepairint, 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类题目时建议先明确几个关键点连通性定义四连通/八连通是否需要保留原数组是否需要统计连通块属性网格规模对算法选择的影响