[LeetCode] 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 <= A.length <= 500
1 <= A[i].length <= 500
0 <= A[i][j] <= 1
All rows have the same size.

飞地的数量。

给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。

移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-enclaves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题意不难理解，就是变相的flood fill类型的题目。这里我给出BFS和DFS两种解法，时间复杂度均为O(mn)，空间复杂度均为O(n)。如果代码看不懂，请先移步200题。无论是哪种做法，基本思路都是先找matrix边界上的1，然后traverse，并且把遇到的1改成一个其他的数字。再一次遍历matrix，如果matrix中还有1，就说明这些1是无法按规则访问到matrix边界并且离开matrix的。

BFS

 1 class Solution {
 2     public int numEnclaves(int[][] A) {
 3         int m = A.length;
 4         int n = A[0].length;
 5         Queue<int[]> queue = new LinkedList<>();
 6         for (int i = 0; i < m; i++) {
 7             for (int j = 0; j < n; j++) {
 8                 if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
 9                     if (A[i][j] == 1) {
10                         queue.offer(new int[] { i, j });
11                     }
12                 }
13             }
14         }
15 
16         while (!queue.isEmpty()) {
17             int[] cur = queue.poll();
18             int x = cur[0];
19             int y = cur[1];
20             if (x < 0 || y < 0 || x >= m || y >= n || A[x][y] != 1) {
21                 continue;
22             }
23             A[x][y] = 2;
24             queue.offer(new int[] { x - 1, y });
25             queue.offer(new int[] { x + 1, y });
26             queue.offer(new int[] { x, y - 1 });
27             queue.offer(new int[] { x, y + 1 });
28         }
29 
30         int count = 0;
31         for (int i = 0; i < m; i++) {
32             for (int j = 0; j < n; j++) {
33                 if (A[i][j] == 1) {
34                     count++;
35                 }
36             }
37         }
38         return count;
39     }
40 }

DFS

 1 class Solution {
 2     public int numEnclaves(int[][] A) {
 3         int m = A.length;
 4         int n = A[0].length;
 5         for (int i = 0; i < m; i++) {
 6             for (int j = 0; j < n; j++) {
 7                 if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
 8                     dfs(A, i, j);
 9                 }
10             }
11         }
12 
13         int count = 0;
14         for (int i = 0; i < m; i++) {
15             for (int j = 0; j < n; j++) {
16                 if (A[i][j] == 1) {
17                     count++;
18                 }
19             }
20         }
21         return count;
22     }
23 
24     private void dfs(int[][] matrix, int i, int j) {
25         if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) {
26             return;
27         }
28         if (matrix[i][j] == 1) {
29             matrix[i][j] = 2;
30             dfs(matrix, i - 1, j);
31             dfs(matrix, i + 1, j);
32             dfs(matrix, i, j - 1);
33             dfs(matrix, i, j + 1);
34         }
35     }
36 }

flood fill题型总结

LeetCode 题目总结