题目

力扣-200-岛屿数量
力扣-695-岛屿最大面积
力扣-1254-封闭岛屿数量

思路讲解

labuladong-一文搞定岛屿问题

岛屿数量

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
42
43
44
45
46
47
48
func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }
    if len(grid[0]) == 0 {
        return 0
    }

    // 记录总的结果
    res := 0
    m := len(grid)
    n := len(grid[0])
    for i := 0; i<m; i++ {
        for j := 0; j<n; j++ {
            if grid[i][j] == '1' {
                res++
                toWater(grid, i, j)
            }
        }
    }

    return res
}

func toWater(grid [][]byte, i, j int) {
    m := len(grid)
    n := len(grid[0])
    
    var dfs func(grid [][]byte, r, c int)
    dfs = func(grid [][]byte, r, c int) {
        if r < 0 || c < 0 || r >= m || c >= n {
            return
        }

        // 已经是海水
        if grid[r][c] == '0' {
            return
        }
        // 遍历过的陆地转为海水
        grid[r][c] = '0'

        dfs(grid, r-1, c)
        dfs(grid, r+1, c)
        dfs(grid, r, c-1)
        dfs(grid, r, c+1)
    }
    dfs(grid, i, j)
}

岛屿最大面积

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
42
43
44
45
func maxAreaOfIsland(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    maxIsland := 0

    for i:=0; i<m; i++ {
        for j:=0; j<n; j++ {
            if grid[i][j] == 1 {
                nowIsland := toWater(grid, i, j)
                if nowIsland > maxIsland {
                    maxIsland = nowIsland
                }
            }
        }
    }

    return maxIsland
}

func toWater(grid [][]int, i, j int) int {
    m := len(grid)
    n := len(grid[0])
    sum := 0
    
    var dfs func(grid [][]int, r, c int)
    dfs = func(grid [][]int, r, c int) {
        if r < 0 || c < 0 || r>=m || c >= n {
            return
        }

        if grid[r][c] == 0 {
            return
        }
        sum++
        grid[r][c] = 0

        dfs(grid, r-1, c)
        dfs(grid, r+1, c)
        dfs(grid, r, c-1)
        dfs(grid, r, c+1)
    }
    dfs(grid, i, j)

    return sum
}

封闭岛屿数量

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
42
43
44
45
46
47
48
49
50
51
52
func closedIsland(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])

    // 把第一行和最后一行的岛屿转为海水
    for j := 0; j<n; j++ {
        toWater(grid, 0, j)
        toWater(grid, m-1, j)
    }

    // 把第一列和最后一列转为海水
    for i := 0; i<m; i++ {
        toWater(grid, i, 0)
        toWater(grid, i, n-1)
    }

    res := 0
    for i :=0; i<m; i++ {
        for j := 0; j<n; j++ {
            if grid[i][j] == 0 {
                res++
                toWater(grid,i,j)
            }
        }
    }

    return res
}

func toWater(grid [][]int, i, j int) {
    m := len(grid)
    n := len(grid[0])

    var dfs func(grid [][]int, r, c int)
    dfs = func(grid [][]int, r, c int) {
        if r < 0 || c < 0 || r >=m || c >=n {
            return
        }
        if grid[r][c] == 1 {
            return
        }

        grid[r][c] = 1

        dfs(grid, r, c-1)
        dfs(grid, r, c+1)
        dfs(grid, r-1, c)
        dfs(grid, r+1, c)
    }
    dfs(grid, i, j)
    return
}