題目

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.

題目大意

給出一個二維數組 A，每個單元格為 0（代表海）或 1（代表陸地）。移動是指在陸地上從一個地方走到另一個地方（朝四個方向之一）或離開網格的邊界。返回網格中無法在任意次數的移動中離開網格邊界的陸地單元格的數量。

提示：

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