【Leetcode】岛屿问题——dfs算法

岛屿问题是dfs回溯算法中的经典问题，以下就是对岛屿问题相关的问题进行汇总。

岛屿问题

463. 岛屿的周长

1.题目描述

leetcode题目链接：463. 岛屿的周长

2.思路分析

3.参考代码

200. 岛屿数量

1.题目描述

leetcode题目链接：200. 岛屿数量

2.思路分析

顺序遍历，若为岛屿 grid[i][j] == 1，则res++，然后将与此位置岛屿相连的陆地置为1，

dfs()思路如下

• 若遇到边界或者水域，终止
• 令陆地变为水域grid[i][j] == 0，然后递归遍历四个方向

3.参考代码

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

305. 岛屿数量Ⅱ

1.题目描述

leetcode题目链接：plus会员题目，可以直接看题目描述。

2.思路分析

3.参考代码

695. 岛屿的最大面积

1.题目描述

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

2.思路分析

3.参考代码

1254. 统计封闭岛屿的数目

1.题目描述

leetcode题目链接：1254. 统计封闭岛屿的数目

2.思路分析

3.参考代码

827. 最大人工岛

1.题目描述

leetcode题目链接：827. 最大人工岛

2.思路分析

3.参考代码