最短的桥
- swfoodt
- Leet code , 每日一题
- June 3, 2022
内容目录
934. 最短的桥
题目分析
| 下面是一个水域 | 左上角有一个岛 | 右下角有一个岛 | 找到两岛间的桥 |
|---|---|---|---|
| 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
大致想法：我们不需要将两个岛全部都找到，只需要找到第一个岛，然后从这个岛开始扩张，每次向外扩张一圈，直到找到第二个岛，那么我们的扩张次数就是这两个岛间的最短的桥了
逐步实现：
首先是如何找到第一个岛？
我们可以先使用广度优先算法：
- 首先遍历二维数组得到第一个 1 的位置（这就意味着我们摸到了第一个岛的一个角）
/**
* @param {number[][]} grid
* @return {number}
*/
var shortestBridge = function (grid) {
for (let i = 0; i < edge; i++) {
for (let j = 0; j < edge; j++) {
if (grid === 1) {
// 找到第一个岛
}
}
}
};
找到这个岛之后，我们需要知道这个岛具体有多大？它的边界在哪里？
我们可以使用广度优先算法来找到这个岛的全貌：我们现在得到了这个岛的一个 1，将它放入一个“待搜查”队列 queue 中，对于 queue 队列中的每一个点我们搜查它周围所有的 1 ，新找到的 1 也放入 queue 队列，用完的 1 扔给 island 数组，直到 queue 中没有点排队了，这样我们就将整个岛都纳入 island 数组了。
/**
* @param {number[][]} grid
* @return {number}
*/
var shortestBridge = function (grid) {
let edge = grid.length; // 水域的边界
let island = []; // 存放岛的数组
let queue = []; //存放待搜查的点的队列
let qlen; //队列的长度
let help = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
]; //帮助我们找到周围的点的数组
let step = 0; //步数
for (let i = 0; i < edge; i++) {
for (let j = 0; j < edge; j++) {
if (grid[i][j] === 1) {
grid[i][j] = 2; //将找到的岛的点标记为2，以防止重复搜索
qlen = queue.push([i, j]); //排队等待搜查
whlie(qlen != 0); //若全搜查完毕就跳出循环
{
let check = queue.shift(); //取出排在最前面的点
qlen--;
let x = check[0];
let y = check[1]; //保存
island.push(check); //放入岛的数组中
for (let k = 0; k < 4; k++) {
//四次循环找上下左右的邻居
let nbx = x + help[k][0];
let nby = y + help[k][1]; //找到邻居的坐标
//判断邻居是否在水域内，且是否为岛
if (
nbx >= 0 &&
nby >= 0 &&
nbx < edge &&
nby < edge &&
grid[nbx][nby] === 1
) {
queue.push([nbx, nby]); //如果是就让去排队等待检查
qlen++;
grid[nbx][nby] = 2; //改变标记
}
}
}
}
}
}
};
通过这些工作，我们就找到了第一个岛，并把岛的所有点的坐标都存在了 island 数组中，接下来我们就可以开始扩张去找第二个岛了。
还是使用广度优先算法来扩张，每一次扩张遍历 island 数组，检查每一个点的四周，如果是水域，就将它划入岛的范围内，直到某一次扩张遇到了第二个岛，这时候我们扩张的次数就是最短的桥的长度了。
/**
* @param {number[][]} grid
* @return {number}
*/
var shortestBridge = function (grid) {
let edge = grid.length; // 水域的边界
let island = []; // 存放岛的数组
let queue = []; //存放待搜查的点的队列
let qlen; //队列的长度
let help = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
]; //帮助我们找到周围的点的数组
let step = 0; //步数
for (let i = 0; i < edge; i++) {
for (let j = 0; j < edge; j++) {
if (grid[i][j] === 1) {
grid[i][j] = 2; //将找到的岛的点标记为2，以防止重复搜索
qlen = queue.push([i, j]); //排队等待搜查
while (qlen != 0) {
//若全搜查完毕就跳出循环
let check = queue.shift(); //取出排在最前面的点
qlen--;
let x = check[0];
let y = check[1]; //保存
island.push(check); //放入岛的数组中
for (let k = 0; k < 4; k++) {
//四次循环找上下左右的邻居
let nbx = x + help[k][0];
let nby = y + help[k][1]; //找到邻居的坐标
//判断邻居是否在水域内，且是否为岛
if (
nbx >= 0 &&
nby >= 0 &&
nbx < edge &&
nby < edge &&
grid[nbx][nby] === 1
) {
queue.push([nbx, nby]); //如果是就让去排队等待检查
qlen++;
grid[nbx][nby] = 2; //改变标记
}
}
}
for (let n of island) {
queue.push(n); //将岛的所有点都放入队列中
}
while (queue.length != 0) {
//开始第二次广度优先搜索
//在每一轮的扩张中队列的长度是不变的，新增的点需要在下一轮扩张中被检查
let qlen = queue.length;
for (let k = 0; k < qlen; k++) {
//每一轮扩张
let check = queue.shift();
let x = check[0];
let y = check[1];
for (let l = 0; l < 4; l++) {
//四次循环找上下左右的邻居
let nbx = x + help[l][0];
let nby = y + help[l][1];
if (nbx >= 0 && nby >= 0 && nbx < edge && nby < edge) {
if (grid[nbx][nby] === 1) {
//如果找到岛，直接返回次数
console.log(step + "===");
return step;
} else if (grid[nbx][nby] === 0) {
//如果是水域，就将它划入岛的范围内
queue.push([nbx, nby]);
grid[nbx][nby] = 2;
}
}
}
}
step++; //每一轮扩张结束后步数加一
}
}
}
}
};
总结
这一题中寻找第一个岛全部点还可以使用深度优先算法，有时间的时候可以尝试一下。
本题的广度优先思想使用了两次，一次是在获取所有岛的点，一次是在扩张岛的范围。两者有一个共同点： 虽说都是基于现有的点来计算，但是被计算的主体并不是 island 数组。究竟哪些点需要计算其周围的情况，是由 queue 队列来决定的。 这是控制时间与空间复杂度的关键。一个 queue 队列可以减少大量的重复运算。