面试题 16.19. 水域大小

题目描述

你有一个用于表示一片土地的整数矩阵 land，该矩阵中每个点的值代表对应地点的海拔高度。若值为 0 则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

示例：

输入：

[
  [0,2,1,0],
  [0,1,0,1],
  [1,1,0,1],
  [0,1,0,1]
]

输出： [1,2,4]

提示：

0 < len(land) <= 1000
0 < len(land[i]) <= 1000

解法一：BFS

 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


func pondSizes(land [][]int) []int {
    if len(land) == 0 || len(land[0]) == 0 {
        return []int{}
    }
    h, w := len(land), len(land[0])

    dirs := [][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}}
    var bfs func(x, y int) int
    bfs = func(x, y int) int {
        var queue [][2]int
        queue = append(queue, [2]int{x, y})
        land[x][y] = 1
        cnt := 1
        for len(queue) > 0 {
            curX, curY := queue[0][0], queue[0][1]
            queue = queue[1:]
            for i := 0; i < len(dirs); i++ {
                dx, dy := dirs[i][0], dirs[i][1]
                nx, ny := curX+dx, curY+dy
                if nx >= 0 && nx < h && ny >= 0 && ny < w && land[nx][ny] == 0 {
                    land[nx][ny] = 1
                    queue = append(queue, [2]int{nx, ny})
                    cnt++
                }
            }
        }
        return cnt
    }

    var ans []int
    for x := 0; x < h; x++ {
        for y := 0; y < w; y++  {
            if land[x][y] == 0 {
                ans = append(ans, bfs(x, y))
            }
        }
    }
    sort.Ints(ans)
    return ans
}

官方题解如下：

 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


func pondSizes(land [][]int) []int {
    m, n := len(land), len(land[0])
    bfs := func(x, y int) int {
        q, res := [][]int{}, 0
        q, land[x][y] = append(q, []int{x, y}), -1
        for len(q) > 0 {
            x, y, q = q[0][0], q[0][1], q[1:]
            res++
            for dx := -1; dx <= 1; dx++ {
                for dy := -1; dy <= 1; dy++ {
                    if dx == 0 && dy == 0 {
                        continue
                    }
                    if x + dx < 0 || x + dx >= m || y + dy < 0 || y + dy >= n || land[x + dx][y + dy] != 0 {
                        continue
                    }
                    land[x + dx][y + dy] = -1
                    q = append(q, []int{x + dx, y + dy})
                }
            }
        }
        return res
    }
    res := []int{}
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if land[i][j] == 0 {
                res = append(res, bfs(i, j))
            }
        }
    }
    sort.Ints(res)
    return res
}

解法二：DFS

 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


func min(nums ...int) int {
    res := nums[0]
    for _, val := range nums {
        if val < res {
            res = val
        }
    }
    return res
}

func pondSizes(land [][]int) []int {
    if len(land) == 0 || len(land[0]) == 0 {
        return []int{}
    }
    h, w := len(land), len(land[0])

    dirs := [][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}}
    var dfs func(x, y int) int
    dfs = func(x, y int) int {
        land[x][y] = 1
        ret := 1
        for i := 0; i < len(dirs); i++ {
            dx, dy := dirs[i][0], dirs[i][1]
            nx, ny := x+dx, y+dy
            if nx >= 0 && nx < h && ny >= 0 && ny < w && land[nx][ny] == 0 {
                ret += dfs(nx, ny)
            }
        }
        return ret
    }

    var ans []int
    for x := 0; x < h; x++ {
        for y := 0; y < w; y++ {
            if land[x][y] == 0 {
                ans = append(ans, dfs(x, y))
            }
        }
    }
    sort.Ints(ans)
    return ans
}

另一种实现代码：

 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


func pondSizes(land [][]int) []int {
    if len(land) == 0 || len(land[0]) == 0 {
        return []int{}
    }
    h, w := len(land), len(land[0])

    dirs := [][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}}
    var dfs func(x, y int) int
    dfs = func(x, y int) int {
        if land[x][y] != 0 {
            return 0
        }
        land[x][y] = 1
        ret := 1
        for i := 0; i < len(dirs); i++ {
            dx, dy := dirs[i][0], dirs[i][1]
            nx, ny := x+dx, y+dy
            if nx >= 0 && nx < h && ny >= 0 && ny < w {
                ret += dfs(nx, ny)
            }
        }
        return ret
    }

    var ans []int
    for x := 0; x < h; x++ {
        for y := 0; y < w; y++ {
            if land[x][y] == 0 {
                ans = append(ans, dfs(x, y))
            }
        }
    }
    sort.Ints(ans)
    return ans
}

官方题解如下：

 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


func pondSizes(land [][]int) []int {
    m, n := len(land), len(land[0])
    var dfs func(int, int) int
    dfs = func(x, y int) int {
        if x < 0 || x >= m || y < 0 || y >= n || land[x][y] != 0 {
            return 0
        }
        land[x][y] = -1
        res := 1
        for dx := -1; dx <= 1; dx++ {
            for dy := -1; dy <= 1; dy++ {
                if dx == 0 && dy == 0 {
                    continue
                }
                res += dfs(x + dx, y + dy)
            }
        }
        return res
    }
    res := []int{}
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if land[i][j] == 0 {
                res = append(res, dfs(i, j))
            }
        }
    }
    sort.Ints(res)
    return res
}