lc1020-飞地的数量

题目描述

• 给定一个 n x m 的二进制矩阵 grid，0表示海洋，1表示陆地
• 相邻的陆地可以走，计算走不到边界的陆地的数量

示例

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3

输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0

题解

• 思路
  1. flood fill，从边界往里“淹”（下面的解是这个思路）
  2. 并查集，把与边界连通的合并到一个集合中，剩下的 1 的个数即为答案，写起来没有 flood fill 方便

var (dx = [4]int{-1, 0, 1, 0}dy = [4]int{0, 1, 0, -1}n, m int
)func numEnclaves(grid [][]int) int {n, m = len(grid), len(grid[0])for i := 0; i < n; i ++ {for j := 0; j < m; j ++ {if (i == 0 || i == n-1 || j == 0 || j == m-1) && grid[i][j] == 1 {dfs(i, j, grid)}}}res := 0for i := 0; i < n; i ++ {for j := 0; j < m; j ++ {res += grid[i][j]}}return res
}func dfs(x, y int, grid [][]int) {grid[x][y] = 0for d := 0; d < 4; d ++ {r, c := x + dx[d], y + dy[d]if 0 <= r && r < n && 0 <= c && c < m && grid[r][c] == 1 {dfs(r, c, grid)}}
}