给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1:

输入: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 都在边界上或可以到达边界。
思考:题目的意思就是只要值为1的块不能通过其它的1到达边界或者不在边界,那么他就是一块飞地,解法就是从最外面的1开始像里找,所找到的1变成0,最后在统计一下值为1的块有多少
class Solution {
public int numEnclaves(int[][] grid) {
int ans = 0;
for (int i =0;i<grid.length; i++){
for (int j=0; j<grid[i].length;j++){
if (i==0||j==0||i==grid.length-1||j==grid[0].length-1&&grid[i][j]==1){
dfs(grid,i,j);
}
}
}
for (int i =0;i<grid.length; i++){
for (int j=0; j<grid[0].length;j++){
if (grid[i][j] == 1) {
ans++;
}
}
}
return ans;
}
public void dfs(int[][] grid, int i, int j) {
if (i<0 || i>= grid.length || j>= grid[i].length || j<0 || grid[i][j]==0){
return;
}
grid[i][j]=0;
dfs(grid, i-1,j);
dfs(grid, i+1,j);
dfs(grid, i,j-1);
dfs(grid, i,j+1);
}
}
这是深度优先的解法,我还去看了一下广度优先的解法,大致思路差不多。也写一下0
public static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int numEnclaves(int[][] grid) {
//定义长度
int m = grid.length, n = grid[0].length;
//定义矩阵标识
boolean[][] visited = new boolean[m][n];
//定义队列
Queue<int[]> queue = new ArrayDeque<int[]>();
//查找值为1的节点 设置布尔值为true 放入队列
for (int i = 0; i < m; i++) {
if (grid[i][0] == 1) {
visited[i][0] = true;
queue.offer(new int[]{i, 0});
}
if (grid[i][n - 1] == 1) {
visited[i][n - 1] = true;
queue.offer(new int[]{i, n - 1});
}
}
//查找值为1的节点 设置布尔值为true 放入队列
for (int j = 1; j < n - 1; j++) {
if (grid[0][j] == 1) {
visited[0][j] = true;
queue.offer(new int[]{0, j});
}
if (grid[m - 1][j] == 1) {
visited[m - 1][j] = true;
queue.offer(new int[]{m - 1, j});
}
}
//队列while循环, 判断不为空值循环
while (!queue.isEmpty()) {
//poll() 删除队列中第一个元素,并返回该元素的值,如果元素为null,将返回null(其实调用的是pollFirst())
int[] cell = queue.poll();
//currRow = i currCol=j
int currRow = cell[0], currCol = cell[1];
for (int[] dir : dirs) {
//防止边界跨域
int nextRow = currRow + dir[0], nextCol = currCol + dir[1];
//查找此节点四周是否存在值为1的节点
if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]) {
visited[nextRow][nextCol] = true;
queue.offer(new int[]{nextRow, nextCol});
}
}
}
int enclaves = 0;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] == 1 && !visited[i][j]) {
enclaves++;
}
}
}
return enclaves;
}