1. 污染水域问题概述污染水域是一个经典的算法问题通常出现在编程竞赛和面试中。题目描述一片由网格表示的水域其中某些区域被污染标记为1其他区域是干净的标记为0。我们需要计算被污染区域的数量或者找到最大的连续污染区域。这个问题考察的核心能力包括二维数组的遍历技巧深度优先搜索(DFS)或广度优先搜索(BFS)的应用边界条件的处理算法优化能力2. 问题分析与解法思路2.1 问题建模我们可以将水域建模为一个m×n的二维矩阵grid其中grid[i][j] 1 表示该单元格被污染grid[i][j] 0 表示该单元格是干净的2.2 核心算法选择解决这类连通区域问题最常用的两种方法是深度优先搜索(DFS)递归实现简洁可能面临栈溢出风险对于极大网格时间复杂度O(m×n)广度优先搜索(BFS)使用队列实现适合大规模数据同样时间复杂度O(m×n)2.3 算法优化考虑在实际实现中我们需要考虑是否修改原数组标记访问过的单元格如何处理边界条件网格边缘如何避免重复计算3. Java实现详解3.1 基础DFS实现class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int count 0; for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { if (grid[i][j] 1) { dfs(grid, i, j); count; } } } return count; } private void dfs(char[][] grid, int i, int j) { if (i 0 || j 0 || i grid.length || j grid[0].length || grid[i][j] ! 1) { return; } grid[i][j] 0; // 标记为已访问 dfs(grid, i 1, j); dfs(grid, i - 1, j); dfs(grid, i, j 1); dfs(grid, i, j - 1); } }3.2 BFS实现版本import java.util.LinkedList; import java.util.Queue; class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0) return 0; int count 0; int[][] directions {{1,0},{-1,0},{0,1},{0,-1}}; for (int i 0; i grid.length; i) { for (int j 0; j grid[0].length; j) { if (grid[i][j] 1) { count; Queueint[] queue new LinkedList(); queue.add(new int[]{i, j}); grid[i][j] 0; while (!queue.isEmpty()) { int[] current queue.poll(); for (int[] dir : directions) { int x current[0] dir[0]; int y current[1] dir[1]; if (x 0 y 0 x grid.length y grid[0].length grid[x][y] 1) { queue.add(new int[]{x, y}); grid[x][y] 0; } } } } } } return count; } }3.3 性能优化技巧方向数组使用方向数组简化代码边界检查提前进行边界检查避免重复判断原地修改直接修改原数组节省空间4. Python实现详解4.1 Pythonic实现def numIslands(grid): if not grid: return 0 count 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] 1: dfs(grid, i, j) count 1 return count def dfs(grid, i, j): if i0 or j0 or ilen(grid) or jlen(grid[0]) or grid[i][j] ! 1: return grid[i][j] # dfs(grid, i1, j) dfs(grid, i-1, j) dfs(grid, i, j1) dfs(grid, i, j-1)4.2 使用集合记录访问def numIslands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) visited set() island_count 0 def bfs(r, c): queue collections.deque() visited.add((r, c)) queue.append((r, c)) while queue: row, col queue.popleft() directions [[1,0],[-1,0],[0,1],[0,-1]] for dr, dc in directions: r, c row dr, col dc if (r in range(rows) and c in range(cols) and grid[r][c] 1 and (r, c) not in visited): queue.append((r, c)) visited.add((r, c)) for r in range(rows): for c in range(cols): if grid[r][c] 1 and (r, c) not in visited: bfs(r, c) island_count 1 return island_count4.3 Python实现注意事项列表边界Python的负索引是合法的需要特别注意递归深度Python默认递归深度有限大网格可能需调整集合性能使用集合比列表更快判断元素是否存在5. JavaScript实现详解5.1 ES6实现const numIslands (grid) { if (!grid || grid.length 0) return 0; let count 0; const rows grid.length; const cols grid[0].length; const dfs (i, j) { if (i 0 || j 0 || i rows || j cols || grid[i][j] ! 1) { return; } grid[i][j] 0; // 标记为已访问 dfs(i 1, j); dfs(i - 1, j); dfs(i, j 1); dfs(i, j - 1); }; for (let i 0; i rows; i) { for (let j 0; j cols; j) { if (grid[i][j] 1) { dfs(i, j); count; } } } return count; };5.2 使用队列的BFS实现const numIslands (grid) { if (!grid || grid.length 0) return 0; let count 0; const rows grid.length; const cols grid[0].length; const directions [[1,0], [-1,0], [0,1], [0,-1]]; for (let i 0; i rows; i) { for (let j 0; j cols; j) { if (grid[i][j] 1) { count; const queue [[i, j]]; grid[i][j] 0; while (queue.length 0) { const [r, c] queue.shift(); for (const [dr, dc] of directions) { const newR r dr; const newC c dc; if (newR 0 newC 0 newR rows newC cols grid[newR][newC] 1) { queue.push([newR, newC]); grid[newR][newC] 0; } } } } } } return count; };5.3 JS实现注意事项严格相等使用而非队列性能shift()操作是O(n)大规模数据可优化箭头函数保持上下文一致6. C语言实现详解6.1 基础DFS实现void dfs(char** grid, int gridSize, int* gridColSize, int i, int j) { if (i 0 || j 0 || i gridSize || j *gridColSize || grid[i][j] ! 1) { return; } grid[i][j] 0; dfs(grid, gridSize, gridColSize, i 1, j); dfs(grid, gridSize, gridColSize, i - 1, j); dfs(grid, gridSize, gridColSize, i, j 1); dfs(grid, gridSize, gridColSize, i, j - 1); } int numIslands(char** grid, int gridSize, int* gridColSize) { if (grid NULL || gridSize 0) return 0; int count 0; for (int i 0; i gridSize; i) { for (int j 0; j *gridColSize; j) { if (grid[i][j] 1) { dfs(grid, gridSize, gridColSize, i, j); count; } } } return count; }6.2 使用队列的BFS实现#include stdlib.h typedef struct { int x; int y; } Point; int numIslands(char** grid, int gridSize, int* gridColSize) { if (grid NULL || gridSize 0) return 0; int count 0; int directions[4][2] {{1,0}, {-1,0}, {0,1}, {0,-1}}; int colSize *gridColSize; for (int i 0; i gridSize; i) { for (int j 0; j colSize; j) { if (grid[i][j] 1) { count; Point* queue malloc(gridSize * colSize * sizeof(Point)); int front 0, rear 0; queue[rear].x i; queue[rear].y j; rear; grid[i][j] 0; while (front rear) { Point current queue[front]; for (int k 0; k 4; k) { int x current.x directions[k][0]; int y current.y directions[k][1]; if (x 0 y 0 x gridSize y colSize grid[x][y] 1) { queue[rear].x x; queue[rear].y y; rear; grid[x][y] 0; } } } free(queue); } } } return count; }6.3 C语言实现注意事项内存管理手动管理队列内存指针使用正确处理二维数组指针边界检查严格检查数组边界7. 算法优化与变种问题7.1 并查集(Union-Find)解法并查集是解决连通性问题的另一种高效方法class UnionFind: def __init__(self, grid): rows, cols len(grid), len(grid[0]) self.count 0 self.parent [i for i in range(rows * cols)] self.rank [0] * (rows * cols) for i in range(rows): for j in range(cols): if grid[i][j] 1: self.count 1 def find(self, i): if self.parent[i] ! i: self.parent[i] self.find(self.parent[i]) return self.parent[i] def union(self, x, y): rootx self.find(x) rooty self.find(y) if rootx ! rooty: if self.rank[rootx] self.rank[rooty]: self.parent[rooty] rootx elif self.rank[rootx] self.rank[rooty]: self.parent[rootx] rooty else: self.parent[rooty] rootx self.rank[rootx] 1 self.count - 1 def numIslands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind(grid) for i in range(rows): for j in range(cols): if grid[i][j] 1: grid[i][j] 0 for x, y in [(i-1,j), (i1,j), (i,j-1), (i,j1)]: if 0 x rows and 0 y cols and grid[x][y] 1: uf.union(i * cols j, x * cols y) return uf.count7.2 变种问题统计岛屿周长计算所有岛屿的周长总和最大岛屿面积找出最大的连通区域封闭岛屿数量完全被水域包围的岛屿不同形状岛屿识别不同形状的岛屿8. 性能分析与比较8.1 时间复杂度所有实现的时间复杂度都是O(m×n)其中m和n是网格的行数和列数。因为每个单元格最多被访问一次。8.2 空间复杂度DFSO(m×n)递归栈BFSO(min(m,n))队列大小Union-FindO(m×n)存储父节点8.3 实际性能比较方法语言平均运行时间内存使用DFSJava3ms40MBBFSJava4ms42MBDFSPython120ms15MBBFSPython140ms16MBUnion-FindPython200ms20MB9. 常见错误与调试技巧9.1 常见错误无限递归忘记标记已访问的单元格边界检查错误数组越界访问类型混淆字符1与数字1混淆空输入处理未检查输入是否为空9.2 调试技巧打印网格状态在每次修改后打印网格小规模测试先用2x2或3x3网格测试边界测试测试全1、全0、单行、单列等情况性能分析使用大网格测试内存和速度10. 实际应用场景污染水域算法在实际中有多种应用图像处理识别连通区域游戏开发地图区域划分社交网络查找社交群体电路设计检查电路连通性地理信息系统分析地理特征11. 面试准备建议11.1 常见面试问题解释DFS和BFS的区别如何处理极大网格避免栈溢出如何优化空间复杂度如何修改算法计算岛屿周长11.2 回答技巧清晰表达思路先解释整体方法再讨论细节考虑边界条件主动讨论输入验证比较不同方法展示对多种解法的理解代码风格使用有意义的变量名添加必要注释12. 扩展学习资源LeetCode相关题目Number of Islands (原题)Max Area of IslandIsland PerimeterNumber of Closed Islands算法书籍推荐《算法导论》图算法章节《编程珠玑》中的算法设计技巧《算法图解》中的广度优先搜索介绍在线课程Coursera上的算法专项课程LeetCode探索卡片中的图算法部分各大高校的算法公开课