X

LEETCODE 1568. Minimum Number of Days to Disconnect Island 解题思路分析

题目大意:

使陆地分离的最少天数

给你一个由若干 0 和 1 组成的二维网格 grid ,其中 0 表示水,而 1 表示陆地。岛屿由水平方向或竖直方向上相邻的 1 (陆地)连接形成。

如果 恰好只有一座岛屿 ,则认为陆地是 连通的 ;否则,陆地就是 分离的 。

一天内,可以将任何单个陆地单元(1)更改为水单元(0)。

返回使陆地分离的最少天数。

示例 1:

输入:grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
输出:2
解释:至少需要 2 天才能得到分离的陆地。
将陆地 grid[1][1] 和 grid[0][2] 更改为水,得到两个分离的岛屿。

示例 2:

输入:grid = [[1,1]]
输出:2
解释:如果网格中都是水,也认为是分离的 ([[1,1]] -> [[0,0]]),0 岛屿。

示例 3:

输入:grid = [[1,0,1,0]]
输出:0

示例 4:

输入:grid = [[1,1,0,1,1],
  [1,1,1,1,1],
  [1,1,0,1,1],
  [1,1,0,1,1]]
输出:1

示例 5:

输入:grid = [[1,1,0,1,1],
  [1,1,1,1,1],
  [1,1,0,1,1],
  [1,1,1,1,1]]
输出:2

提示:

  • 1 <= grid.length, grid[i].length <= 30
  • grid[i][j]01

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1568

解题思路分析:

首先我想给这道题一个差评。周赛时题目给出的条件似乎并不严谨(不知道以后题目会不会做出修改),比如当只存在一个岛屿并且该岛屿中只存在1个或者2个1时,那么我们无论如何也无法分割。比如[[1,1]]。因此本题解法不考虑此情况。

首先我们应该明确一点,将一个岛屿分割成两个或以上的方式,最多只需要2天时间。这个很好证明,比如我们可以找到岛屿的一个凸角(最多有2条边与岛屿其他部分相连),此时我们只要切断这两条边,那么这个凸角将独立成为新的岛屿。

有了这个前提,题目就变得简单了许多。大致步骤如下:

  1. 首先使用bfs查看岛屿数量(具体如何查看后文介绍)。如果数量大于1,直接返回0。
  2. 尝试将每个1变为0,然后再使用bfs查看岛屿数量,如果数量大于1,说明,改变当前土地即可实现切割。因此可返回1。
  3. 上述以外情况返回2。

最后我们再来说下如何判断岛屿数量,其实这是经典的bfs染色问题(如果你对bfs还不了解,强烈建议你去参考一下这篇文章:LEETCODE常见算法之广度优先搜索BFS超详细白话讲解)。首先我们循环二维数组,找到任意一个值为1的点,然后通过该点开始进行bfs操作,bfs扩散的条件为相邻格子的值为1,同时bfs扩散所到之处,我们将1变为0。这样,bfs结束之后,我们会将当前岛屿整体染色为0(都变为海洋)。这时我们再遍历一遍数组,如果数组中还存在1,那么说明还存在其他岛屿,即当前存在多个岛屿。

实现代码:

public int minDays(int[][] grid) {
    if(!isSingleIslands(grid)) return 0; // 如果存在多个岛屿,不用操作,返回0
    for(int i=0;i<grid.length;i++){ // 循环地图中每一个点
        for(int j=0;j<grid[0].length;j++){
            if(grid[i][j]==1){ // 如果当前是陆地
                grid[i][j]=0; // 尝试将当前陆地变为海洋
                // 改变后,如果存在多个岛屿,返回1。
                // 即只改变当前位置即可实现题目要求
                if(!isSingleIslands(grid)) return 1;
                // 否则,将当前还原为1,继续尝试下一个点
                grid[i][j]=1;
            }
        }
    }
    return 2;
}
// 查看是否只有一个岛屿
boolean isSingleIslands(int[][] grid){
    // 复制一份地图
    int[][] copy=new int[grid.length][grid[0].length];
    // 找到一个土地的位置(任意土地位置都行),作为bfs起始位置
    int firstR=0,firstC=0;
    for(int i=0;i<grid.length;i++){
        for(int j=0;j<grid[0].length;j++){
            copy[i][j]=grid[i][j]; // 复制地图
            if(copy[i][j]==1){ // 找到一个土地的位置
                firstR=i;
                firstC=j;
            }
        }
    }
    // bfs的4个方向
    int[][] dirs=new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    // bfs用到的Queue
    Queue<int[]> q = new LinkedList<>();
    // 将bfs起始位置设置为海洋
    copy[firstR][firstC]=0;
    // 将起始位置加入Queue
    q.offer(new int[]{firstR, firstC});
    // 以下为bfs常规操作
    while(q.size()>0){
        int[] pos = q.poll(); // 取出一个位置
        int row=pos[0], col=pos[1];
        for(int dir[] : dirs){ // 从该位置向4周扩散
            int r=row+dir[0], c=col+dir[1]; // 扩散后的位置
            // 如果该位置没有越界,且该位置为土地
            if(r>=0&&r<copy.length&&c>=0&&c<copy[0].length&&copy[r][c]==1){
                copy[r][c]=0;  // 将该位置变为海洋
                q.offer(new int[]{r,c});  // 将该位置加入到bfs的Queue中,等待下一步扩散
            }
        }
    }
    // bfs后再循环一遍数组
    for(int i=0;i<copy.length;i++){
        for(int j=0;j<copy[0].length;j++){
            // 如果还存在陆地,说明岛屿数量大于1,返回false
            if(copy[i][j]==1) return false;
        }
    }
    return true;
}

本题解法执行时间为50ms。

Runtime: 50 ms, faster than 71.43% of Java online submissions for Minimum Number of Days to Disconnect Island.

Memory Usage: 39.5 MB, less than 14.29% of Java online submissions for Minimum Number of Days to Disconnect Island.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1568-minimum-number-of-days-to-disconnect-island-解题思路分析/
Categories: leetcode
kwantong: