题目大意：
使陆地分离的最少天数
给你一个由若干 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 <= 30grid[i][j]为0或1
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1568
解题思路分析：
首先我想给这道题一个差评。周赛时题目给出的条件似乎并不严谨（不知道以后题目会不会做出修改），比如当只存在一个岛屿并且该岛屿中只存在1个或者2个1时，那么我们无论如何也无法分割。比如[[1,1]]。因此本题解法不考虑此情况。
首先我们应该明确一点，将一个岛屿分割成两个或以上的方式，最多只需要2天时间。这个很好证明，比如我们可以找到岛屿的一个凸角（最多有2条边与岛屿其他部分相连），此时我们只要切断这两条边，那么这个凸角将独立成为新的岛屿。
有了这个前提，题目就变得简单了许多。大致步骤如下：
- 首先使用bfs查看岛屿数量（具体如何查看后文介绍）。如果数量大于1，直接返回0。
- 尝试将每个1变为0，然后再使用bfs查看岛屿数量，如果数量大于1，说明，改变当前土地即可实现切割。因此可返回1。
- 上述以外情况返回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&©[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-解题思路分析/