在给定的二维二进制数组 A 中,存在两座岛。(岛是由四面相连的 1 形成的一个最大组。)
现在,我们可以将 0 变为 1,以使两座岛连接起来,变成一座岛。
返回必须翻转的 0 的最小数目。(可以保证答案至少是 1。)
示例 1:
输入:[[0,1],[1,0]]
输出:1
示例 2:
输入:[[0,1,0],[0,0,0],[0,0,1]]
输出:2
示例 3:
输入:[[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 <= A.length = A[0].length <= 100
- A[i][j] == 0 或 A[i][j] == 1
题意分析:
在一个矩阵中,有两个岛(相连的1组成),找着两座岛的最短距离。
tips:看到找最短的xx问题,就一定要想到bfs。
思路分析:
我们从一个岛屿出发,用bfs遍历出所有相邻的矩形,直至和另一个岛屿有重叠的部分。如图:
用dfs找出两个岛屿的所在地,用bfs获得最短距离
1 |
|
近期评论