LeetCode 1020.飞地的数量

1.题目：

给你一个大小为 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 都在边界上或可以到达边界。

2.代码：

dfs：

class Solution {
    int[][] move = {{0,1},{0,-1},{1,0},{-1,0}};
    int count=0;
    public int numEnclaves(int[][] grid) {
        for(int i=0;i<grid.length;i++){
            if(grid[i][0]==1){
                dfs(grid,i,0);
            }
            if(grid[i][grid[0].length-1]==1){
                dfs(grid,i,grid[0].length-1);
            }
        }
        for(int j=1;j<grid[0].length-1;j++){
            if(grid[0][j]==1){
                dfs(grid,0,j);
            }
            if(grid[grid.length-1][j]==1){
                dfs(grid,grid.length-1,j);
            }
        }
        count=0;
        for(int i=1;i<grid.length-1;i++){
            for(int j=1;j<grid[0].length-1;j++){
                if(grid[i][j]==1){
                    dfs(grid,i,j);
                }
            }
        }
        return count;
    }
    public void dfs(int[][] grid,int x,int y){
        if(grid[x][y]==0) return;
        grid[x][y]=0;
        count++;
        for(int i=0;i<move.length;i++){
            int m=x+move[i][0];
            int n=y+move[i][1];
            if(m<0||n<0||m>=grid.length||n>=grid[0].length||grid[m][n]==0) continue;
            dfs(grid,m,n);
        }
    }
}

bfs：

class Solution {
    int[][] move = {{0,1},{0,-1},{1,0},{-1,0}};
    int count=0;
    public int numEnclaves(int[][] grid) {
        for(int i=0;i<grid.length;i++){//把左右两边的1变成0
            if(grid[i][0]==1){
                bfs(grid,i,0);
            }
            if(grid[i][grid[0].length-1]==1){//注意这里的宽度是grid[0].length
                bfs(grid,i,grid[0].length-1);
            }
        }
        for(int j=1;j<grid[0].length-1;j++){//把上下两边的1变成0 注意之前重复的不用变了
            if(grid[0][j]==1){
                bfs(grid,0,j);
            }
            if(grid[grid.length-1][j]==1){//注意这里的是长度grid.length-1
                bfs(grid,grid.length-1,j);
            }
        }
        count=0;//计算的也算是总面积
        for(int i=1;i<grid.length-1;i++){
            for(int j=1;j<grid[0].length-1;j++){
                if(grid[i][j]==1){
                    bfs(grid,i,j);
                }
            }
        }
        return count;
    }
    public void bfs(int[][] grid,int x,int y){
       Queue<Integer> queue = new LinkedList<>();
       queue.offer(x);
       queue.offer(y);
       count++;
       grid[x][y]=0;
       while(!queue.isEmpty()){//注意这个判断条件不要忘记了
            int m1 = queue.poll();
           int n1=queue.poll();
 for(int i=0;i<move.length;i++){
          int m=m1+move[i][0];//注意这里要重新用变量，不要直接用抛出来的
           int n=n1+move[i][1];
           if(n<0||m<0||m>=grid.length||n>=grid[0].length||grid[m][n]==0) continue;
          if(grid[m][n]==1){
              queue.offer(m);
              queue.offer(n);
              count++;
              grid[m][n]=0;
          }
       }
       }
      
    }
}