网格 dfs 与 FloodFill：从岛屿、区域到搜索路径

目录

引入：网格 DFS 的共同结构

一、图像渲染：从起点扩散同一种颜色

二、岛屿数量：外层寻找起点，内部淹没整座岛

三、岛屿的最大面积：让 DFS 返回连通块大小

四、被围绕的区域：从边界反向寻找安全区域

五、太平洋大西洋水流问题：从终点反向搜索

六、扫雷游戏：把四方向换成八方向

七、单词搜索：需要恢复当前路径的访问状态

八、黄金矿工和不同路径 III：访问标记就是路径状态

九、从多道网格题中归纳规律

八、易错点

九、本篇总结

引入：网格 DFS 的共同结构

网格题就是在由行和列组成的二维数组中搜索。DFS 是 Depth First Search 的缩写，中文是深度优先搜索，表示从当前位置沿一个方向继续深入，走不通后再返回尝试其他方向。

FloodFill 可以理解成“泛洪填充”：从一个起点向相邻位置扩散，把和起点连通、并且满足条件的格子全部访问或修改。row和col表示当前格子的行号和列号，DIRECTIONS表示移动方向，visited表示某个格子是否已经在当前搜索路径中访问过。

网格题中最容易固定下来的检查顺序是：先判断是否越界，再判断当前格子是否满足条件，然后标记或修改当前格子，最后递归搜索相邻位置。如果题目要求寻找一条具体路径，递归返回后还要恢复标记；如果题目只是处理连通块，修改网格本身通常就可以同时完成访问标记。

一、图像渲染：从起点扩散同一种颜色

题目描述

题目：图像渲染。LeetCode 733。

给定一个二维图像、起点坐标和新颜色，把与起点上下左右连通、并且颜色和起点相同的所有像素改成新颜色。

题目链接：图像渲染

算法原理

先记住起点原来的颜色oldColor。从起点出发，只进入颜色仍然等于oldColor的格子。访问一个格子后立即改成newColor，这样它既完成了染色，也不会被后续递归再次处理。

如果新旧颜色相同，改色后无法区分已经访问和还没有访问的位置，因此可以直接返回原图像。

Java 代码

class Solution { private static final int[][] DIRECTIONS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; public int[][] floodFill(int[][] image, int sr, int sc, int color) { int oldColor = image[sr][sc]; if (oldColor == color) return image; dfs(image, sr, sc, oldColor, color); return image; } private void dfs(int[][] image, int row, int col, int oldColor, int newColor) { if (row < 0 || row >= image.length || col < 0 || col >= image[0].length || image[row][col] != oldColor) { return; } image[row][col] = newColor; for (int[] direction : DIRECTIONS) { dfs(image, row + direction[0], col + direction[1], oldColor, newColor); } } }

代码说明

DIRECTIONS中的四组数字分别表示向上、向下、向左和向右移动。direction[0]是行变化量，direction[1]是列变化量。

递归入口先取得起点颜色。dfs先进行越界和颜色判断，通过后把当前格子改成新颜色，再遍历四个方向。改色动作放在递归之前，所以同一个格子不会重复扩散。

二、岛屿数量：外层寻找起点，内部淹没整座岛

题目描述

题目：岛屿数量。LeetCode 200。

给定一个由'1'和'0'组成的网格，其中'1'表示陆地，'0'表示水。上下左右连接的陆地属于同一座岛屿，返回岛屿数量。

题目链接：岛屿数量

算法原理

外层双重循环负责逐个检查网格。遇到一个还没有处理的'1'，就说明发现了一座新岛屿，答案加一，然后从这个位置开始 DFS，把整座相连的岛屿都标记为已经处理。

代码把访问过的陆地改成'0'。这样同一座岛屿中的其他格子即使之后被外层循环遇到，也不会再次增加答案。

Java 代码

class Solution { private static final int[][] DIRECTIONS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; public int numIslands(char[][] grid) { int ret = 0; for (int row = 0; row < grid.length; row++) { for (int col = 0; col < grid[0].length; col++) { if (grid[row][col] == '1') { ret++; dfs(grid, row, col); } } } return ret; } private void dfs(char[][] grid, int row, int col) { if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] != '1') { return; } grid[row][col] = '0'; for (int[] direction : DIRECTIONS) { dfs(grid, row + direction[0], col + direction[1]); } } }

代码说明

ret表示已经发现的岛屿数量。外层循环发现一个'1'后，先让ret++，再调用dfs把这座岛屿的所有陆地改成'0'。

这里的dfs不需要返回面积或路径，只负责把当前连通块处理完。外层“发现新起点”和内层“扩散整块区域”是两个不同职责，分开后不容易重复计数。

三、岛屿的最大面积：让 DFS 返回连通块大小

题目描述

题目：岛屿的最大面积。LeetCode 695。

给定一个由 0 和 1 组成的网格，1 表示陆地，0 表示水。上下左右连接的陆地属于同一座岛屿，返回面积最大的岛屿面积。

题目链接：岛屿的最大面积

算法原理

这道题和岛屿数量使用相同的连通块搜索，只是 DFS 的返回值不同。当前陆地格子本身贡献 1，再加上上下左右四个方向能够访问到的陆地数量，就是从当前格子出发的岛屿面积。

访问当前格子后把它改成 0，避免同一块陆地被重复计算。外层循环对每个未处理的陆地调用面积 DFS，再用Math.max保留最大值。

Java 代码

class Solution { public int maxAreaOfIsland(int[][] grid) { int ret = 0; for (int row = 0; row < grid.length; row++) { for (int col = 0; col < grid[0].length; col++) { if (grid[row][col] == 1) { ret = Math.max(ret, dfs(grid, row, col)); } } } return ret; } private int dfs(int[][] grid, int row, int col) { if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0) { return 0; } grid[row][col] = 0; return 1 + dfs(grid, row - 1, col) + dfs(grid, row + 1, col) + dfs(grid, row, col - 1) + dfs(grid, row, col + 1); } }

代码说明

递归出口返回 0，表示越界或当前格子不是陆地，不会给面积增加贡献。合法陆地格子先改成 0，然后返回1加四个方向的面积。

Math.max(ret, dfs(...))会比较当前最大面积和新发现岛屿的面积，保留较大值。Math.max是 JavaMath工具类中的方法，用来返回两个数中较大的一个。

四、被围绕的区域：从边界反向寻找安全区域

题目描述

题目：被围绕的区域。LeetCode 130。

给定一个由X和O组成的二维棋盘，把所有被X包围的O改成X。与边界相连的O不会被包围，应保持不变。

题目链接：被围绕的区域

算法原理

直接寻找每个被包围的区域不太容易判断，因此可以反过来寻找“绝对安全”的区域。边界上的O一定不会被包围，从所有边界O出发做 DFS，把能够连接到边界的O暂时标记为A。

扫描整个棋盘时，剩下的O都没有连接到边界，可以改成X；暂时标记为A的位置再恢复为O。

Java 代码

class Solution { private static final int[][] DIRECTIONS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; public void solve(char[][] board) { if (board.length == 0) return; int rows = board.length; int cols = board[0].length; for (int row = 0; row < rows; row++) { dfs(board, row, 0); dfs(board, row, cols - 1); } for (int col = 0; col < cols; col++) { dfs(board, 0, col); dfs(board, rows - 1, col); } for (int row = 0; row < rows; row++) { for (int col = 0; col < cols; col++) { if (board[row][col] == 'O') { board[row][col] = 'X'; } else if (board[row][col] == 'A') { board[row][col] = 'O'; } } } } private void dfs(char[][] board, int row, int col) { if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != 'O') { return; } board[row][col] = 'A'; for (int[] direction : DIRECTIONS) { dfs(board, row + direction[0], col + direction[1]); } } }

代码说明

边界循环可能会重复访问角落，但dfs只有遇到'O'才会继续，所以不会产生错误。标记A的意思是“和边界相连、需要保留”。

最后一次遍历把普通O改成X，把A恢复成O。这类题的关键不是改变 DFS，而是先把题目条件转换成“从边界寻找安全连通块”。

五、太平洋大西洋水流问题：从终点反向搜索

题目描述

题目：太平洋大西洋水流问题。LeetCode 417。

给定一个高度矩阵，水可以从高度较高或相等的格子流向高度较低或相等的相邻格子。矩阵上边和左边连接太平洋，下边和右边连接大西洋，返回能够让水流到两个海洋的所有格子。

题目链接：太平洋大西洋水流问题

算法原理

如果从每个格子出发模拟水流，重复搜索很多次。可以反过来从两个海洋的边界出发，沿着“高度不下降”的方向向内搜索。

某个格子如果能够从太平洋边界被搜索到，说明水可以从这个格子流向太平洋；同理，能够从大西洋边界搜索到，说明水可以流向大西洋。最后同时被两个访问数组标记的位置就是答案。

Java 代码

class Solution { private static final int[][] DIRECTIONS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; public List<List<Integer>> pacificAtlantic(int[][] heights) { int rows = heights.length; int cols = heights[0].length; boolean[][] pacific = new boolean[rows][cols]; boolean[][] atlantic = new boolean[rows][cols]; for (int row = 0; row < rows; row++) { dfs(heights, row, 0, pacific); dfs(heights, row, cols - 1, atlantic); } for (int col = 0; col < cols; col++) { dfs(heights, 0, col, pacific); dfs(heights, rows - 1, col, atlantic); } List<List<Integer>> ret = new ArrayList<>(); for (int row = 0; row < rows; row++) { for (int col = 0; col < cols; col++) { if (pacific[row][col] && atlantic[row][col]) { ret.add(Arrays.asList(row, col)); } } } return ret; } private void dfs(int[][] heights, int row, int col, boolean[][] visited) { if (visited[row][col]) return; visited[row][col] = true; for (int[] direction : DIRECTIONS) { int nextRow = row + direction[0]; int nextCol = col + direction[1]; if (nextRow < 0 || nextRow >= heights.length || nextCol < 0 || nextCol >= heights[0].length) { continue; } if (heights[nextRow][nextCol] < heights[row][col]) { continue; } dfs(heights, nextRow, nextCol, visited); } } }

代码说明

pacific和atlantic分别记录能够从两个海洋反向到达的位置。visited是当前这次反向搜索的访问标记，不是回溯路径标记，因为同一个海洋的搜索中，某个位置访问一次后结果就已经确定。

反向移动时，下一格高度必须大于等于当前格高度。原本水是从高处流向低处，反过来搜索就要从低处走向高处。

六、扫雷游戏：把四方向换成八方向

题目描述

题目：扫雷游戏。LeetCode 529。

给定一个扫雷棋盘和点击位置。如果点击到雷，将其标记为X；如果点击到空白位置，根据周围八个方向的雷数显示数字。如果周围没有雷，则继续展开相邻空白区域。

题目链接：扫雷游戏

算法原理

扫雷使用八个方向，而不是常见的上下左右四个方向。点击空白格时先统计周围八个位置的雷数；如果雷数大于 0，显示对应数字；如果雷数为 0，把当前格标记为B，再继续搜索八个方向。

Java 代码

class Solution { private static final int[][] DIRECTIONS = { {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1} }; public char[][] updateBoard(char[][] board, int[] click) { dfs(board, click[0], click[1]); return board; } private void dfs(char[][] board, int row, int col) { if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] != 'E') { return; } int mines = 0; for (int[] direction : DIRECTIONS) { int nextRow = row + direction[0]; int nextCol = col + direction[1]; if (nextRow >= 0 && nextRow < board.length && nextCol >= 0 && nextCol < board[0].length && board[nextRow][nextCol] == 'M') { mines++; } } if (mines > 0) { board[row][col] = (char) ('0' + mines); return; } board[row][col] = 'B'; for (int[] direction : DIRECTIONS) { dfs(board, row + direction[0], col + direction[1]); } } }

代码说明

DIRECTIONS中的八组变化量覆盖了当前格周围的所有位置。只有还没有处理的空白格'E'才会继续递归，雷和已经显示的格子不会重复处理。

(char) ('0' + mines)把 1 到 8 的数字转换成字符。周围有雷时只显示数量，不再向外扩散；周围没有雷时标记为B，再搜索八个方向。

七、单词搜索：需要恢复当前路径的访问状态

题目描述

题目：单词搜索。LeetCode 79。

给定一个字符网格和一个单词，判断能否通过上下左右相邻的格子依次组成这个单词。同一个格子在一条路径中不能重复使用。

题目链接：单词搜索

算法原理

外层双重循环把每个格子都作为起点尝试。递归状态包括当前匹配到的单词下标index、当前行列坐标以及visited标记。

先判断越界、当前格是否已经在路径中、当前字符是否匹配。通过判断后标记当前格，再递归四个方向。若四个方向都失败，取消当前格的标记，返回上一层尝试其他选择。

Java 代码

class Solution { private static final int[][] DIRECTIONS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; public boolean exist(char[][] board, String word) { boolean[][] visited = new boolean[ board.length][board[0].length]; for (int row = 0; row < board.length; row++) { for (int col = 0; col < board[0].length; col++) { if (dfs(board, word, 0, row, col, visited)) { return true; } } } return false; } private boolean dfs(char[][] board, String word, int index, int row, int col, boolean[][] visited) { if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || visited[row][col] || board[row][col] != word.charAt(index)) { return false; } if (index == word.length() - 1) return true; visited[row][col] = true; for (int[] direction : DIRECTIONS) { if (dfs(board, word, index + 1, row + direction[0], col + direction[1], visited)) { visited[row][col] = false; return true; } } visited[row][col] = false; return false; } }

代码说明

index表示当前要匹配单词中的哪个字符。找到最后一个字符时可以直接返回true。其他情况下，当前格先标记为已访问，再去寻找下一个字符。

这里必须恢复visited[row][col] = false。即使某条路径失败，也要恢复；如果找到答案后提前返回，也要恢复当前标记，避免共享的访问数组留下不必要的状态。

八、黄金矿工和不同路径 III：访问标记就是路径状态

题目描述

题目：黄金矿工。LeetCode 1219。

在一个网格中从任意有黄金的格子出发，每次只能上下左右移动，不能进入没有黄金的格子，也不能重复访问格子，返回能够收集到的最大黄金数量。

题目链接：黄金矿工

题目：不同路径 III。LeetCode 980。

给定一个网格，从起点走到终点，要求经过所有可走的空格恰好一次，返回满足条件的路径数量。

题目链接：不同路径 III

算法原理

这两道题都不是简单的连通块统计，因为“当前走过哪些格子”会影响后面的选择。同一个坐标，如果已经走过的格子不同，未来能走的路线也不同，所以需要在递归过程中维护访问状态，并在返回后撤销。

黄金矿工的递归返回从当前格出发还能获得的最大黄金，进入格子后把它暂时改成 0，四个方向尝试结束后恢复原来的黄金值。不同路径 III 还需要记录剩余必须经过的格子数量，走到终点时只有剩余数量满足要求才算一条完整路径。

Java 代码

class Solution { private static final int[][] DIRECTIONS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; public int getMaximumGold(int[][] grid) { int ret = 0; for (int row = 0; row < grid.length; row++) { for (int col = 0; col < grid[0].length; col++) { if (grid[row][col] != 0) { ret = Math.max(ret, dfs(grid, row, col)); } } } return ret; } private int dfs(int[][] grid, int row, int col) { if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0) { return 0; } int gold = grid[row][col]; grid[row][col] = 0; int best = 0; for (int[] direction : DIRECTIONS) { best = Math.max(best, dfs(grid, row + direction[0], col + direction[1])); } grid[row][col] = gold; return gold + best; } }

代码说明

gold暂存当前格子的黄金数量，随后把当前格改成 0，表示本条路径不能再次进入。四个方向都尝试完成后，把gold写回去，这就是路径级状态恢复。

和岛屿面积题不同，黄金矿工不能永久把格子改成 0，因为其他起点或其他路径还需要使用这个格子。是否恢复状态，要看题目要求的是“整个搜索过程只处理一次”，还是“每条候选路径都可以重新尝试”。

九、从多道网格题中归纳规律

图像渲染、岛屿数量和最大面积都可以看成连通块问题。外层寻找新的起点，内部 DFS 扩散整块区域；访问标记可以通过修改网格完成。它们的差别主要是返回值：图像渲染修改颜色，岛屿数量返回连通块个数，最大面积返回连通块大小。

被围绕的区域和太平洋大西洋水流问题都使用了“反向思考”。被围绕的区域从边界找安全区域，水流问题从海洋边界反向寻找能够到达的位置。很多网格题的难点不在 DFS 代码，而在于找到合适的搜索起点。

单词搜索、黄金矿工和不同路径 III属于路径型回溯。此时visited或网格修改只在当前路径有效，递归返回后必须恢复。扫雷的主要变化是方向从四方向扩展到八方向。

因此遇到网格题时，可以先判断三个问题：移动方向是四方向还是八方向？访问过的格子是整个搜索过程都不能再处理，还是只在当前路径中不能重复？DFS 需要返回数量、最大值、真假，还是只修改网格？这三个问题通常能确定代码骨架。

八、易错点

1. 访问数组元素前没有先判断行列是否越界。
2. 忘记标记访问，导致相邻格子之间反复递归。
3. 四方向和八方向混淆。
4. FloodFill 新旧颜色相同时仍然继续扩散。
5. 岛屿数量没有在发现新起点后淹没整座岛，造成重复计数。
6. 被围绕的区域没有从边界寻找安全的O。
7. 单词搜索、黄金矿工等路径题修改状态后没有恢复。
8. 把visited和memo混淆：visited限制当前路径，memo保存状态答案。

九、本篇总结

网格 DFS 的固定骨架可以概括为“确定起点、判断边界、判断格子、标记访问、沿方向递归”。连通块题通常可以永久标记，路径题通常必须在递归返回后恢复。题目看起来可能是染色、岛屿、棋盘或路径，但只要先确认移动方向、访问范围和返回结果，往往都能还原出相同的搜索结构。