写点什么

leetcode 934. Shortest Bridge 最短的桥 (中等)

作者:okokabcd
  • 2022 年 6 月 07 日
  • 本文字数:1562 字

    阅读完需:约 5 分钟

leetcode 934. Shortest Bridge 最短的桥(中等)

一、题目大意

标签: 搜索


https://leetcode.cn/problems/shortest-bridge


在给定的二维二进制数组 A 中,存在两座岛。(岛是由四面相连的 1 形成的一个最大组。)


现在,我们可以将 0 变为 1,以使两座岛连接起来,变成一座岛。


返回必须翻转的 0 的最小数目。(可以保证答案至少是 1 。)


示例 1:


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


示例 2:


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


示例 3:


输入:A = [[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


提示:


  • 2 <= A.length == A[0].length <= 100

  • A[i][j] == 0 或 A[i][j] == 1

二、解题思路

给一个二维的矩阵,0 表示海洋 1 表示陆地,上面一共有两个小岛,由竖连接着的 1 组成的。现在填多少格子让两个小岛连在一起。这道题可以看成多起点多终点的最短路径问题。这种情况我们可以使用 BFS(广度优先搜索),把起点全部 push 到队列里面去,下一步走到终点上的放就找到路径了,就是一个 BFS 找最短路径的问题。前提是知道哪部分是起点,哪部分是终点。起点我们可以使用 DFS 来找,找到小岛后标记成 2。然后往外扩展,每次往外扩一层,直到碰到 1 为止。


以题目中的示例 2 为例,如上图左上角第二个。使用 DFS 找到第 1 个小岛后标记成 2,放到 queue 里去,这是起点。然后用 BFS 去扩展,使小岛面积不断的扩大,每次往外扩一层,直到碰到 1 为止。上图当扩展到第 3 步即第 3 层的时候碰到 1 了,说明找到了路径了,即两个岛的最短距离为 3-1=2。

三、解题方法

3.1 Java 实现

public class Solution {    public int shortestBridge(int[][] grid) {        // 用来存入第一个岛屿的坐标        Queue<Pair> queue = new LinkedList();        boolean found = false;        for (int i = 0; !found && i < grid.length; i++) {            for (int j = 0; !found && j < grid[0].length; j++) {                if (grid[i][j] == 1) {                    dfs(grid, j, i, queue);                    found = true;                }            }        }
int steps = 0; int[] dirs = new int[]{0, 1, 0, -1, 0}; while (!queue.isEmpty()) { int size = queue.size(); while (size-- != 0) { Pair p = queue.poll(); int x = p.x; int y = p.y; for (int i = 0; i < 4; i++) { int tx = x + dirs[i]; int ty = y + dirs[i + 1]; if (tx < 0 || ty < 0 || tx >= grid[0].length || ty >= grid.length || grid[ty][tx] == 2) { continue; } if (grid[ty][tx] == 1) { return steps; } grid[ty][tx] = 2; queue.add(new Pair(tx, ty)); } } steps++; }
return -1; }
private void dfs(int[][] grid, int x, int y, Queue<Pair> queue) { if (x < 0 || y < 0 || x >= grid[0].length || y >= grid.length || grid[y][x] != 1) { return; } grid[y][x] = 2; queue.add(new Pair(x, y)); dfs(grid, x - 1, y, queue); dfs(grid, x, y - 1, queue); dfs(grid, x + 1, y, queue); dfs(grid, x, y + 1, queue); }
class Pair { int x; int y;
public Pair(int x, int y) { this.x = x; this.y = y; } }
}
复制代码

四、总结小记

  • 2022/6/7 要总结一些模板

发布于: 刚刚阅读数: 3
用户头像

okokabcd

关注

还未添加个人签名 2019.11.15 加入

还未添加个人简介

评论

发布
暂无评论
leetcode 934. Shortest Bridge 最短的桥(中等)_LeetCode_okokabcd_InfoQ写作社区