1020. Number of Enclaves

# 1020. Number of Enclaves#

## 题目 #

Given a 2D array `A`, each cell is 0 (representing sea) or 1 (representing land)

A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.

Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.

Example 1:

``````Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation:
There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.
``````

Example 2:

``````Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation:
All 1s are either on the boundary or can reach the boundary.
``````

Note:

1. `1 <= A.length <= 500`
2. `1 <= A[i].length <= 500`
3. `0 <= A[i][j] <= 1`
4. All rows have the same size.

## 题目大意 #

• 1 <= A.length <= 500
• 1 <= A[i].length <= 500
• 0 <= A[i][j] <= 1
• 所有行的大小都相同

## 解题思路 #

• 给出一个地图，要求输出不和边界连通的 1 的个数。
• 这一题可以用 DFS 也可以用并查集解答。DFS 的思路是深搜的过程中把和边界连通的点都覆盖成 0，最后遍历一遍地图，输出 1 的个数即可。并查集的思路就比较直接了，把能和边界连通的放在一个集合中，剩下的就是不能和边界连通的都在另外一个集合中，输出这个集合里面元素的个数即可。
• 这一题和第 200 题，第 1254 题，第 695 题类似。可以放在一起练习。

## 代码 #

``````func numEnclaves(A [][]int) int {
m, n := len(A), len(A[0])
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i == 0 || i == m-1 || j == 0 || j == n-1 {
if A[i][j] == 1 {
dfsNumEnclaves(A, i, j)
}
}
}
}
count := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if A[i][j] == 1 {
count++
}
}
}
return count
}

func dfsNumEnclaves(A [][]int, x, y int) {
if !isInGrid(A, x, y) || A[x][y] == 0 {
return
}
A[x][y] = 0
for i := 0; i < 4; i++ {
nx := x + dir[i][0]
ny := y + dir[i][1]
dfsNumEnclaves(A, nx, ny)
}
}

``````

Sep 6, 2020