岛屿问题，矩阵：DFS+标记剪枝+回溯

• 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
• 剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。
• 在矩阵深度优先算法中，DFS方法总有参数：横坐标 i 、 纵坐标 j 、待匹配的参数，这样才可以进行自由地深度优先算法（方便指定方向、指定待匹配参数）
• 在矩阵深度优先算法中，每个位置都可以作为递归的起点，因此main方法中需要两层for循环来实现

一些区别：

• 虽然都涉及标记已经遍历过的位置，但 是否存在的匹配问题，每轮（不同起点）执行后都需要恢复；而像“岛屿数量”这种计数问题，则不能恢复
• 虽然都要遍历上下左右(调用4个方向的dfs)，但“是否存在匹配”的问题只要一个匹配就算成功，所以涉及到回溯，用 || 连接四个方向的dfs结果

1.剑指12

1.1题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

1.2题解

• 每轮(以不同元素为起点)的标记行为，不能影响其他轮次，因此顺序必须是标记-DFS-恢复
• DFS中先考虑边界条件：4个边界(false) or 字符串到末尾了(true)

。

class Solution {
    public boolean exist(char[][] board, String word) {
            char[] arr = word.toCharArray();
            for(int i = 0 ; i < board.length ; i++){
                for(int j = 0 ; j < board[0].length ; j++){
                    if( dfs(board, i ,j , arr, 0) ){ return true};
                }
            }
            return false;
    }

    //判断i j位置上word的第index号元素是否匹配
    public boolean dfs(char[][] board , int i , int j , char[] word,int index){
        /**因为涉及递归，条件需要写全 */
        //矩阵边界 false
        if(i<0 || j<0 || i>=board.length || j>=board[0].length){return false;}
        //当前不匹配 false
        if(word[index] != board[i][j]){return false;}
        //字符串匹配到了末尾 true
        if(index == word.length-1){return true;}
        /**如果没到末尾，就先标记当前位置，再往四个方向递归 */
        board[i][j] = '\0';//只要不是A~Z 字母就行，注意转义  '.'也可以

        //因为是递归，如果存在匹配成功，总有一个DFS的末端返回true，回溯都返回true
        //所以用||来处理回溯结果
        boolean currentRes = dfs(board, i+1 ,j ,word , index+1) ||
                            dfs(board, i ,j+1 ,word , index+1) ||
                            dfs(board, i-1 ,j ,word , index+1) ||
                            dfs(board, i ,j-1 ,word , index+1) ;
        board[i][j] = word[index];
        return currentRes;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2.力扣200

2.1题目描述

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

2.2题解

class Solution {
    public int numIslands(char[][] grid) {
        //空值
        if(grid == null || grid.length == 0 || grid[0].length == 0){ return 0;}
        int sum = 0;
        //以每个位置为起点，每次都dfs将当前岛屿全部置为0
        for(int i = 0 ; i < grid.length ; i++){
            for(int j = 0 ; j < grid[0].length ; j++){
                if(grid[i][j] == '1'){
                    //当前位置为1时，计数+1，相邻所有1变为0
                    sum++;
                    dfs(grid , i , j);
                }
            }
        }
        return sum;
    }

    //将相邻的所有1变为0，每次递归都对上下左右暴力置0
    public void dfs(char[][] grid, int i, int j){
        //越界直接返回
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length){return;}
        //本来就是0也直接返回
        if(grid[i][j] == '0'){return;}
        //当前是1，置为0后上下左右dfs
        grid[i][j] = '0';
        dfs(grid , i+1 , j);
        dfs(grid , i-1 , j);
        dfs(grid , i , j+1);
        dfs(grid , i , j-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3.力扣463

3.1题目描述

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

3.2题解

核心就是：陆地（1）旁边如果越界、或者是海洋（0），那么计数+1
我们可以将DFS算法返回值为void，直接对静态变量进行操作；也可以将DFS方法返回值设为int，用回溯来做

3.2.1操作静态变量

class Solution {
    static int sum = 0;
    public int islandPerimeter(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0){return 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);
                }
            }
        }
        return sum;
    }



    public void dfs(int[][] grid , int i , int j ){
        //若当前位置不是陆地，那么周长+1
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0){
            sum++;
            return;
            }
        
        //如果当前是陆地，那么周长总计不变，继续上下左右遍历
        //所到之处标为2：需要标记，且不能标记为0,  0会被计数
        if(grid[i][j] == 1){
            grid[i][j] = 2;
            dfs(grid, i+1 , j );
            dfs(grid, i-1 , j );
            dfs(grid, i , j+1 );
            dfs(grid, i , j-1 );
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

3.2.2用回溯

class Solution {
    public int islandPerimeter(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0){return 0;}
        for(int i = 0 ; i < grid.length ; i++){
            for(int j = 0 ; j < grid[0].length ; j++){
                if(grid[i][j] == 1){
                   return dfs(grid , i , j);
                }
            }
        }
        return 0;
    }

    public int dfs(int[][] grid , int i , int j ){
        //若当前位置越界，那么周长+1，且需要返回
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length ){
            return 1;
            }
        if( grid[i][j] == 0){
            return 1;
        }
        
        //如果当前是陆地，那么周长总计不变，继续上下左右遍历
        //所到之处标为2：需要标记，且不能标记为0,  0会被计数
        if(grid[i][j] == 1){
            grid[i][j] = 2;
            return
            dfs(grid, i+1 , j )+
            dfs(grid, i-1 , j )+
            dfs(grid, i , j+1 )+
            dfs(grid, i , j-1 );
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

4.力扣695

4.1题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

4.2题解

同样的DFS+回溯统计结果

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
       //空值
        if(grid == null || grid.length == 0 ||grid[0].length == 0){
            return 0;
        }
        //最大面积
        int max = 0;
        int temp = 0;
        for(int i = 0 ; i < grid.length ; i++){
            for(int j = 0 ; j < grid[0].length ; j++){
                if(grid[i][j] == 1){
                    //该轮dfs的面积值
                   temp = dfs(grid,i,j);
                   if(temp > max){
                       max = temp;
                   }
                }
            }
        }
        return max;
    }

    public int dfs(int[][] grid , int i , int j ){
        //越界or海洋  则返回0
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0){
            return 0;
        }
        //每轮dfs的返回值总
        if(grid[i][j] == 1){
            grid[i][j] = 2;
            //回溯，注意要加上自身（+1）
            return 1+
            dfs(grid , i+1 , j )+
            dfs(grid , i-1 , j )+
            dfs(grid , i , j+1 )+
            dfs(grid , i , j-1 );
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41