目录引入网格 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 ListListInteger 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); } ListListInteger 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 需要返回数量、最大值、真假还是只修改网格这三个问题通常能确定代码骨架。八、易错点访问数组元素前没有先判断行列是否越界。忘记标记访问导致相邻格子之间反复递归。四方向和八方向混淆。FloodFill 新旧颜色相同时仍然继续扩散。岛屿数量没有在发现新起点后淹没整座岛造成重复计数。被围绕的区域没有从边界寻找安全的O。单词搜索、黄金矿工等路径题修改状态后没有恢复。把visited和memo混淆visited限制当前路径memo保存状态答案。九、本篇总结网格 DFS 的固定骨架可以概括为“确定起点、判断边界、判断格子、标记访问、沿方向递归”。连通块题通常可以永久标记路径题通常必须在递归返回后恢复。题目看起来可能是染色、岛屿、棋盘或路径但只要先确认移动方向、访问范围和返回结果往往都能还原出相同的搜索结构。
网格 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 ListListInteger 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); } ListListInteger 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 需要返回数量、最大值、真假还是只修改网格这三个问题通常能确定代码骨架。八、易错点访问数组元素前没有先判断行列是否越界。忘记标记访问导致相邻格子之间反复递归。四方向和八方向混淆。FloodFill 新旧颜色相同时仍然继续扩散。岛屿数量没有在发现新起点后淹没整座岛造成重复计数。被围绕的区域没有从边界寻找安全的O。单词搜索、黄金矿工等路径题修改状态后没有恢复。把visited和memo混淆visited限制当前路径memo保存状态答案。九、本篇总结网格 DFS 的固定骨架可以概括为“确定起点、判断边界、判断格子、标记访问、沿方向递归”。连通块题通常可以永久标记路径题通常必须在递归返回后恢复。题目看起来可能是染色、岛屿、棋盘或路径但只要先确认移动方向、访问范围和返回结果往往都能还原出相同的搜索结构。