给定一个二维 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 |
提示
本题实际上是求两个岛屿间的最短距离,因此我们可以先通过任意搜索方法找到其中一个岛屿,然后利用广度优先搜索,查找其与另一个岛屿的最短距离。