关于【网格结构】岛屿类问题的通用解法DFS（深度遍历）遍历框架+回溯+剪枝总结

た入场券 2024-03-26 17:09 20阅读 0赞

##  ##

最近在刷力扣时遇见的问题，自己总结加上看了力扣大佬的知识总结写下本篇文章，我们所熟悉的 DFS（深度优先搜索）问题通常是在树或者图结构上进行的。而我们今天要讨论的 DFS 问题，是在一种「网格」结构中进行的。岛屿问题是这类网格 DFS 问题的典型代表。网格结构遍历起来要比二叉树复杂一些，如果没有掌握一定的方法，DFS 代码容易写得冗长繁杂。

**目录**

一、网格类问题的DFS遍历方法

1.1网格问题基本概念

1.2 DFS的基本结构

1.3 如何避免重复遍历

二、岛屿经典例题

2.1 岛屿数量

2.2 岛屿的周长

2.3 单词搜索

--------------------

## 一、网格类问题的DFS遍历方法 ##

#### 1.1网格问题基本概念 ####

> 网格问题是由 m×n 个小方格组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。 数字为1的格子连接起来就形成一个岛屿。

![650212bee4954fa5860a954fd1986a54.png][]

#### 1.2 DFS的基本结构 ####

> 首先我们要确定访问的下一个节点以及停止的边界，那么首先网格结构中的每个格子可以向四周延伸，分别为上，下，左，右，对于格子(r,c)来说，对应的四个坐标分别为(r+1,c)、(r-1,c)、(r,c-1)、(r,c+1)。

![fc51dbe657254614b55a84e03742b18a.png][]

>  **其次超出格子的边界是什么?是grid\[r\]\[c\]出现下标越界异常的格子，也就是那些超出范围的格子。**

![6556dce87a1d45339020a8299d4f2405.png][]

> 这样我们就得到了网格DFS遍历的框架代码：

public void infect(char[][] grid,int i ,int j){
    //超出范围
            if (i < 0 || i >= grid.length || 
            j < 0 || j >= grid[0].length){
                return;
            }
    //访问上，下，左，右
            infect(grid,i+1,j);
            infect(grid,i-1,j);
            infect(grid,i,j+1);
            infect(grid,i,j-1);
    }

#### 1.3 如何避免重复遍历 ####

> **网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于，遍历中可能遇到遍历过的结点。这是因为，网格结构本质上是一个「图」，我们可以把每个格子看成图中的结点，每个结点有向上下左右的四条边。在图中遍历时，自然可能遇到重复遍历结点。**

![9c21d1e3bc224976a0f009cc06f41a3a.png][]

>  如何避免这样的重复遍历呢？答案是将已经遍历过的格子的值修改一下，每次走过一个格子就修改格子的值。以岛屿问题为例，我们需要在所有值为 1 的陆地格子上做 DFS 遍历。每走过一个陆地格子，就把格子的值改为 2，这样当我们遇到 2 的时候，就知道这是遍历过的格子了。

public void infect(char[][] grid,int i ,int j){
            if (i < 0 || i >= grid.length || 
            j < 0 || j >= grid[0].length ){
                return;
            }
            grid[i][j] = '2';
            infect(grid,i+1,j);
            infect(grid,i-1,j);
            infect(grid,i,j+1);
            infect(grid,i,j-1);
        }

## **二、岛屿经典例题** ##

#### 2.1 岛屿数量 ####

> [岛屿类问题的通用解法、DFS 遍历框架 - 岛屿数量 - 力扣（LeetCode）][DFS _ - _ - _LeetCode]
> 
> ![337693012e3648e79120c9db6a783787.png][]
> 
>  *  0 —— 海洋格子
>  *  1 —— 陆地格子（未遍历过）
>  *  2 —— 陆地格子（已遍历过）

class Solution {
       public int numIslands(char[][] grid) {
            int islandNum = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == '1'){
                        infect(grid,i,j);
                        islandNum++;
                    }
                }
            }
            return islandNum;
        }
        
        public void infect(char[][] grid,int i ,int j){
            if (i < 0 || i >= grid.length || 
            j < 0 || j >= grid[0].length || grid[i][j] != '1'){
                return;
            }
            grid[i][j] = '2';
            infect(grid,i+1,j);
            infect(grid,i-1,j);
            infect(grid,i,j+1);
            infect(grid,i,j-1);
        }
    }

#### 2.2 岛屿的周长 ####

> [463. 岛屿的周长 - 力扣（LeetCode）][463. _ - _LeetCode]
> 
> 给你一个由 `'1'`（陆地）和 `'0'`（水）组成的的二维网格，请你计算网格中岛屿的数量。
> 
> 网格中的格子 **水平和垂直** 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

> 我们可以将岛屿的周长中的边分为两类，如下图所示。黄色的边是与网格边界相邻的周长，而蓝色的边是与海洋格子相邻的周长。
> 
> 当我们的 dfs 函数因为「坐标 (r, c) 超出网格范围」返回的时候，实际上就经过了一条黄色的边；而当函数因为「当前格子是海洋格子」返回的时候，实际上就经过了一条蓝色的边。

![737a43d3d96b4bae801b5c2616b29603.png][]

>  **本题我们可以再次嵌套DFS的框架，但是要增加几处地方，实际上，岛屿的周长是计算岛屿全部的「边缘」，而这些边缘就是我们在 DFS 遍历中，`dfs` 函数返回的位置。**

class Solution {
        public int islandPerimeter(int[][] grid) {
            for (int r = 0; r < grid.length; r++) {
                for (int c = 0; c < grid[0].length; c++) {
                    if (grid[r][c] == 1){
                        return dfs(grid,r,c);
                    }
                }
            }
            return 0;
        }
    
        public int dfs(int[][] grid,int r,int c){
            if (r < 0 || r >= grid.length ||
                    c < 0 || c >= grid[0].length ){
                return 1;
            }
            if (grid[r][c] == 0){
                return 1;
            }
            if (grid[r][c] != 1){
                return 0;
            }
            grid[r][c] = 2;
            return dfs(grid,r-1,c)+dfs(grid,r+1,c)
                    +dfs(grid,r,c-1)+dfs(grid,r,c+1);
        }
    }

#### 2.3 单词搜索 ####

> [79. 单词搜索 - 力扣（LeetCode）][79. _ - _LeetCode]
> 
> 给定一个 `m x n` 二维字符网格 `board` 和一个字符串单词 `word` 。如果 `word` 存在于网格中，返回 `true` ；否则，返回 `false` 。

![7eeca846eb734f4bb2887f5ab889bfba.png][]

>  **本题在使用上面的DFS框架时，要加上回溯，因为当搜索一次时，会更改当前的格子的值，**
> 
> **如果我在DFS的过程中不改矩阵的状态，那我就会出现重复搜索的情况啊，这可不行，因此矩阵是必须得改的。那就只剩下一个办法了，每次DFS的过程中修改矩阵，DFS完了再把矩阵给改回去呗，这就是回溯！**

> **那么什么是剪枝呢？所谓剪枝就是我在dfs的时候，如果已经找到一个正确的路径了，换句话说已经得到结果了，其实就没必要继续DFS了，直接返回结果即可。这就是剪枝。**
> 
> **给一下官方的说法：剪枝，就是减小树的规模，尽早排除搜索树中不必要的分支的一种手段。**

class Solution {
        private boolean find;
        public boolean exist(char[][] board, String word) {
            if(board == null){
                return false;
            }
            int m = board.length,n = board[0].length;
            boolean[][] visited = new boolean[m][n];
            find = false;
    
            for(int i = 0;i < m;i++){
                for(int j = 0 ;j < n;j++){
                    backtracking(i, j, board, word, visited, 0);
                }
            }
            return find;
        }
    
        /**
        * i,j,board：棋盘格及当前元素的坐标
        * word: 要搜索的目标单词
        * visited：记录当前格子是否已被访问过
        * pos: 记录目标单词的字符索引，只有棋盘格字符和pos指向的字符一致时，才有机会继续搜索接下来的字符；如果pos已经过了目标单词的尾部了，那么便说明找到目标单词了
        */
        public void backtracking(int i, int j, char[][] board, String word, boolean[][] visited, int pos){
             // 超出边界、已经访问过、已找到目标单词、棋盘格中当前字符已经和目标字符不一致了
            if(i < 0 || i >= board.length || j <0 || 
            j>=board[0].length || visited[i][j] || 
            find || board[i][j] != word.charAt(pos)){
                return;
            }
            if(pos == word.length()-1){
                find = true;
                return;
            }
    
            visited[i][j] = true;// 修改当前节点状态
            backtracking(i+1, j, board, word, visited, pos+1);  // 遍历子节点
            backtracking(i-1, j, board, word, visited, pos+1);
            backtracking(i, j+1, board, word, visited, pos+1);
            backtracking(i, j-1, board, word, visited, pos+1);
            visited[i][j] = false; // 撤销修改
        }
    }

### 如果对你有帮助，麻烦双击三连一下，谢谢啦！ ###

[650212bee4954fa5860a954fd1986a54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/98e7b728e4f146618626bacf5559ca5b.png
[fc51dbe657254614b55a84e03742b18a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/72a170579a20409c9639e27027723de1.png
[6556dce87a1d45339020a8299d4f2405.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/daa660d3ab0b4d6c939c08ae19c59b2c.png
[9c21d1e3bc224976a0f009cc06f41a3a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/36cd76eaa4a74b178dc21d42d96b1d5d.png
[DFS _ - _ - _LeetCode]: https://leetcode.cn/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/
[337693012e3648e79120c9db6a783787.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/38202c0686dc4124ac9f9b3031b42421.png
[463. _ - _LeetCode]: https://leetcode.cn/problems/island-perimeter/
[737a43d3d96b4bae801b5c2616b29603.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/55cfdabf49584583aa6384d6e7d442e5.png
[79. _ - _LeetCode]: https://leetcode.cn/problems/word-search/
[7eeca846eb734f4bb2887f5ab889bfba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/dc29bd3deaad40b0afa2d0add0ef4c9f.png