1020. Number of Enclaves #

Problem #

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.

Problem Summary #

Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land). A move means walking from one place on land to another place (in one of the four directions), or leaving the boundary of the grid. Return the number of land cells in the grid that cannot leave the boundary of the grid in any number of moves.

Notes:

• 1 <= A.length <= 500
• 1 <= A[i].length <= 500
• 0 <= A[i][j] <= 1
• All rows have the same size

Solution Ideas #

• Given a map, output the number of 1s that are not connected to the boundary.
• This problem can be solved using DFS or Union Find. The DFS idea is to, during the depth-first search, change all points connected to the boundary to 0. Finally, traverse the map once and output the number of 1s. The Union Find idea is relatively straightforward: put those that can be connected to the boundary into one set, and the rest that cannot be connected to the boundary are in another set. Output the number of elements in this set.
• This problem is similar to problem 200, problem 1254, and problem 695. They can be practiced together.

Code #

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)
	}
}