1020. 飞地的数量

/ 0评 / 0

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

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

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

示例 1:

img

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

img

输入: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;
  }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注