【总结】岛屿类问题（二维表格的dfs）

【leetCode 200.】岛屿数量 https://leetcode.cn/problems/number-of-islands/

解题思路

首先，我们要遍历所有的格子，如果当前的格子是岛屿，就递归把这个岛屿所有陆地都遍历出来，然后让数量+1。

那么我们需要处理的最核心的就是 重复遍历 问题，如何保证我们遍历过的陆地不被重复遍历。

其实解决方法也很简单，只要把我们遍历过的陆地做个标记，下次就不会重复遍历了。

具体递归逻辑： 首先确定参数和返回值，参数是当前的二维数组，和进入递归的格子，不需要返回值；
终止条件是当前遍历的格子不是陆地，或者超出了边界；
最后单层处理逻辑是，把当前的陆地做标记，防止多次遍历。

代码

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

【leetCode695 .岛屿最大面积】https://leetcode.cn/problems/max-area-of-island/submissions/

解题思路

岛屿问题变种，依次处理所有的格子，如果当前格子是陆地 并且 没有被遍历过，就进入递归处理。

递归逻辑：

1. 首先确定参数和返回值。参数是当前的格子坐标以及格子数组，返回值是当前岛屿的面积；
2. 确定终止条件：如果当前位置不是陆地或者已经被遍历过了，或者超出了边界，都返回0；
3. 确定单层逻辑：把当前的陆地标记为已遍历，然后递归处理当前格子的相邻格子，最后返回当前岛屿的面积即可。

代码

class Solution {
        public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    int num=dfs(grid, i, j);
                    max=Math.max(max,num);
                }
            }
        }
        return max;
    }

    public int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return 0;
        if (grid[i][j] != 1) return 0;
        grid[i][j] = 2;
        return 1 + dfs(grid, i - 1, j) +
                dfs(grid, i, j - 1) +
                dfs(grid, i + 1, j) +
                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

【leetCode 130】 被围绕的区域 https://leetcode.cn/problems/surrounded-regions/

解题思路

有点类似于岛屿问题变种，也是在二维表格里进行dfs递归，翻译一下题目，其实就是遍历表格，如果当前的字母是“O”并且不和边界“O”相连，就把它变成“X”。
所以我们要做的就是对所有的边界O进行dfs，标记那些和它相连的O，最后遍历表格， 对没有标记的O改为“X”即可。

代码

public class Solution {
    public void solve(char[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            dfs(grid,i,0);
            dfs(grid,i,grid[0].length-1);
        }
        for (int j=1;j<grid[0].length-1;j++){
            dfs(grid,0,j);
            dfs(grid,grid.length-1,j);
        }
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (grid[i][j]=='O')
                    grid[i][j]='X';
                else if (grid[i][j]=='#')
                    grid[i][j]='O';
            }
        }
    }

    public void dfs(char[][] grid, int i, int j) {
        if (i<0 || i>=grid.length || j<0 || j>=grid[0].length) return;
        if (grid[i][j]!='O') return;
        grid[i][j]='#';
        dfs(grid,i+1,j);
        dfs(grid,i,j+1);
        dfs(grid,i-1,j);
        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