esc to dismiss

934. 最短的桥

题目

在给定的二维二进制数组 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

解体思路

这套题可以用 DFS + BFS 来解决,具体方法是:

  1. 首先用 DFS 找出第一个岛,然后用原图减去第一个岛即可得第二个岛。
  2. 从第一个岛上开始用 BFS 来搜索,直到到达第二个岛,长度即为最短的桥长。

经验教训

犯了两个错误:

  1. BFS 里开始我很傻的,从第一个桥每个点遍历一遍,实际上在 BFS 中只需要将 第一个桥的所有点放到待待探索节点队列中即可。
  2. 在 BFS 中没有及时将探索到的店放入已访问节点map (visited)中,导致将节点重复放入待探索节点数组中,造成重复访问,效率很低。
x