给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

    一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

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

    示例 1：
    image.png

    输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
    输出：3
    解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
    示例 2：

    输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
    输出：0
    解释：所有 1 都在边界上或可以到达边界。

    提示：

    m == grid.length
    n == grid[i].length
    1 <= m, n <= 500
    grid[i][j] 的值为 0 或 1

    多源bfs

    1. class Solution {
    2.     /**
    3.     将所有「边缘陆地」看做与超级源点相连，起始将所有「边缘陆地」进行入队（等价于只将超级源点入队，然后取出超级源点并进行拓展）。
    4. 然后是常规的 BFS 过程，所有能够出队/入队的陆地格子，都代表与「边缘陆地」联通，都不属于「飞地」，对其进行标记。
    5. 最后遍历整个棋盘，统计所有未被标记的「陆地」格子数量即是答案。
    6.     */
    7.     static int[] dirs = new int[]{-1,0,1,0,-1};
    8.     public int numEnclaves(int[][] grid) {
    9.         int n = grid.length, m = grid[0].length;
    10.         Deque<int[]> q = new ArrayDeque<>();
    11.         int res = 0;
    12.         for (int i = 0; i < n; ++i) 
    13.             for (int j = 0; j < m; ++j) 
    14.                 if ((i == 0 || i == n-1 || j == 0 || j == m-1) && grid[i][j] == 1) {
    15.                     q.addLast(new int[]{i,j});
    16.                     while (!q.isEmpty()) {
    17.                         int[] t = q.pollFirst();
    18.                         int x = t[0], y = t[1];
    19.                         grid[x][y] = 0;
    20.                         for (int k = 0; k < 4; ++k) {
    21.                             int a = x + dirs[k], b = y + dirs[k+1];
    22.                             if (a < 0 || a >= n || b < 0 || b >= m) 
    23.                                 continue;
    24.                             if (grid[a][b] == 1) q.addLast(new int[]{a,b});
    25.                         }
    26.                     }
    27.                 }
    28.         for (int i = 0; i < n; ++i) 
    29.             for (int j = 0; j < m; ++j) 
    30.                 if (grid[i][j] == 1) res++;
    31.         return res;
    32.     }
    33. }

    并查集&DFS

    1. class Solution {
    2.     int N = 550;
    3.     int[] p = new int[N*N];
    4.     int m,n;
    5.     int[][] g;
    6.     int[] dirs = new int[]{-1,0,1,0,-1};
    8.     int find(int x) {
    9.         if (x != p[x]) p[x] = find(p[x]);
    10.         return p[x];
    11.     }
    13.     boolean query(int x, int y) {
    14.         return find(x) == find(y);
    15.     }
    17.     void union(int x, int y) {
    18.         p[find(x)] = find(y);
    19.     }
    21.     int getIdx(int x, int y) {
    22.         return x * m + y + 1;       //偏移量
    23.     }
    25.     public int numEnclaves(int[][] grid) {
    26.         g = grid;
    27.         n = g.length; m = g[0].length;
    28.         //先初始化并查集,让每个单元格为一个连通块
    29.         for (int i = 0; i < n; ++i) 
    30.             for (int j = 0; j < m; ++j) 
    31.                 p[getIdx(i,j)] = getIdx(i,j);
    32.         //标记边缘陆地
    33.         for (int i = 0; i < n; ++i) 
    34.             for (int j = 0; j < m; ++j) 
    35.                 if (i == 0 || i == n-1 || j == 0 || j == m-1) {
    36.                     if (g[i][j] == 0 || query(getIdx(i,j),0)) continue;
    37.                     dfs(i,j);
    38.                 }
    39.         int res = 0;
    40.         for (int i = 0; i < n; ++i) 
    41.             for (int j = 0; j < m; ++j) 
    42.                 if (g[i][j] == 1 && !query(getIdx(i,j),0)) res++;
    43.         return res;
    44.     }
    45.     void dfs(int x, int y) {
    46.         union(getIdx(x,y),0);
    47.         for (int i = 0; i < 4; ++i) {
    48.             int a = x + dirs[i], b = y + dirs[i+1];
    49.             if (a < 0 || a >= n || b < 0 || b >= m) continue;
    50.             //判重,如果是超级源点块就跳过
    51.             if (g[a][b] == 0 || query(getIdx(a,b),0)) continue;
    52.             dfs(a,b);
    53.         }
    54.     }
    55. }
    1. class Solution {
    2.     int[][] grid;
    3.     int n, m;
    4.     int[] dirs = new int[]{-1, 0, 1, 0, -1};
    5.     public int numEnclaves(int[][] grid) {
    6.         this.grid = grid;
    7.         n = grid.length; m = grid[0].length;
    8.         //直接从边缘的1出发深搜
    9.         for (int i = 0; i < n; ++i) {
    10.             if (grid[i][0] == 1) dfs(i, 0);
    11.             if (grid[i][m - 1] == 1) dfs(i, m - 1);
    12.         }
    13.         for (int i = 0; i < m; ++i) {
    14.             if (grid[0][i] == 1) dfs(0, i);
    15.             if (grid[n - 1][i] == 1) dfs(n - 1, i);
    16.         }
    17.         int res = 0;
    18.         for (int i = 0; i < n; ++i) 
    19.             for (int j = 0; j < m; ++j) 
    20.                 if (grid[i][j] == 1) res++;
    21.         return res;
    22.     }
    24.     void dfs(int x, int y) {
    25.         grid[x][y] = 0;
    26.         for (int i = 0; i < 4; ++i) {
    27.             int a = x + dirs[i], b = y + dirs[i + 1];
    28.             if (a < 0 || a >= n || b < 0 || b >= m) continue;
    29.             if (grid[a][b] == 0) continue;
    30.             dfs(a, b);
    31.         }
    32.     }
    33. }