LC.P1020[飞地的数量]

思路

找出矩阵最外围的陆地(即1)作为源点，向矩阵内部进行BFS搜索，将搜索到的陆地进行标记。

最后遍历矩阵，若为陆地且没有被标记，则为飞地。

方法一：多源BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    static int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    public int numEnclaves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int ans = 0;
        Deque<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
                    if (grid[i][j] == 1) {
                        visited[i][j] = true;
                        queue.offer(new int[]{i, j});
                    }
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                if (grid[nx][ny] != 1) continue;
                if (visited[nx][ny]) continue;
                queue.offer(new int[]{nx, ny});
                visited[nx][ny] = true;
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1 && !visited[i][j]) ++ans;
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(m * n)$
  • 空间复杂度：$O(m * n)$