一、题目
给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
返回必须翻转的 0 的最小数目。
二、示例
2.1> 示例 1：
【输入】grid = [[0,1],[1,0]]
【输出】1
2.2> 示例 2：
【输入】grid = [[0,1,0],[0,0,0],[0,0,1]]
【输出】2
2.3> 示例 3：
【输入】grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
【输出】1
提示：
- n == grid.length == grid[i].length
-
2<= n <=100 - grid[i][j] 为
0或1 - grid 中恰有
两个岛
三、解题思想
本题与《827. 最大人工岛》这道题比较类似。那么，题目中给我们透露出了如下几个关键的信息：
1>
grid中恰有2个岛。那么对于后续我们对岛屿编号的时候，其实只需要针对1个岛屿就可以了。
2> 将任意数量的0变为1，以使两座岛连接起来，变成一座岛。并且返回必须翻转的 0 的最小数目。
那么由于0代表水域，1代表陆地，我们要区分两个岛屿，所以，在遍历grid矩阵的时候，只要第一次发现了某个格子为1，则开始将发现的新大陆进行编号，即：将1变为2。在次过程中，我们采用深度遍历的方式寻找整个岛，在深度遍历的过程中，如果我们发现了某个格子为0，则说明我们已经遍历到了岛屿的边缘部分，则将其也赋值为2，即：将0变为2，与此同时，将这个“边缘的格子”放入到双向队列Deque<int[]> edges中，edges中保存着int[]数组，队列中的每个数组长度都是2，即：int[0]保存这个 “边缘的格子”的行，int[1]保存这个 “边缘的格子”的列。
遍历完整个岛屿之后，我们除了将其赋值为2之外，在队列edges中还保存了这个岛屿的所有“边缘格子”，那么下一步骤，我们就需要开启while循环，即：每次循环都根据edges中保存的这个岛屿的所有“边缘格子”对外进行一层的岛屿扩充操作。即：从edges中出队列每个“边缘格子”，再分别从上/下/右/左，四个方向去查看相邻的格子，如果发现是0，则表明是新的一层边缘格子，将其赋值为2，并将其加入到队列edges中，用于下一次while循环。
在对外一层层的扩展岛屿操作过程中，只要发现有“边缘格子”的四周出现了1，则说明已经与另一个岛屿接壤了，直接返回扩展层数即可。具体操作，如下图所示：
时间复杂度为：O(n^2)，其中 n 表示矩阵的行数/列数。
四、代码实现
class Solution {
int[][] grid, coordinates = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; // 上、下、右、左四个方向
Deque<int[]> edges; // 用户存储边缘格子
public int shortestBridge(int[][] grid) {
int result = 0;
boolean findIsland = false; // 只要找到2个岛屿中其中的1个岛屿，就将其设置为true，并结束步骤1中的两层for循环
edges = new ArrayDeque();
this.grid = grid;
/** 步骤1：为其中一个岛屿打标记（val=2），并保存”边界格子“到edges中 */
for (int i = 0; !findIsland && i < grid.length; i++)
for (int j = 0; !findIsland && j < grid[0].length; j++)
if (findIsland = (grid[i][j] == 1)) markIsland(i, j);
/** 步骤2：利用边界edges，一层一层扩展岛屿（val=2），直到遇到另一个岛屿（val=1）*/
while (!edges.isEmpty()) {
result++; // 扩展层数
int x = 0, y = 0, num = edges.size();
for (int i = 0; i < num; i++) {
int[] edge = edges.removeFirst();
for (int[] c : coordinates) { // 向edge的四个方向查看格子编号，并扩展岛屿边界
int nex = edge[0] + c[0], ney = edge[1] + c[1];
if(isLegal(nex, ney) && grid[nex][ney] == 0) {
edges.addLast(new int[]{nex, ney}); // 添加新的边界
grid[nex][ney] = 2;
}
else if (isLegal(nex, ney) && grid[nex][ney] == 1) return result; // 与另一个岛屿相遇，则直接返回result
}
}
}
return result;
}
public void markIsland(int row, int column) {
if (!isLegal(row, column) || grid[row][column] == 2) return;
if (grid[row][column] == 0) {
grid[row][column] = 2; // 将边界向外扩展1层岛屿（val=2)
edges.addLast(new int[]{row, column});
return;
}
grid[row][column] = 2; // 为岛屿打标记（val=2）
for (int[] c : coordinates) markIsland(row + c[0], column + c[1]); // 深度遍历某个格子的四个方向
}
public boolean isLegal(int row, int column) {
return row >= 0 && row < grid.length && column >= 0 && column < grid[0].length;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论