欢迎24级新生

2212. Shortest Bridge (Medium)

给定一个二维 0-1 矩阵,其中 1 表示陆地,0 表示海洋,每个位置与上下左右相连。已知矩阵中有且只有两个岛屿,求最少要填海造陆多少个位置才可以将两个岛屿相连。

输入

输入是一个二维整数数组

输出

输出是一个非负整数,表示需要填海造陆的位置数

样例

标准输入 复制文本
[[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

提示

本题实际上是求两个岛屿间的最短距离,因此我们可以先通过任意搜索方法找到其中一个岛屿,然后利用广度优先搜索,查找其与另一个岛屿的最短距离。

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 0
通过 0