难度:★★★★☆
类型:数组
方法:深度优先搜索,宽度优先搜索
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
在给定的二维二进制数组 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
解答
这类问题在二维数组的搜索方式中算比较复杂了,最重要的是理清思路。
比较容易理解的方法是:
第一步:我们可以找到两座岛屿,并将组成这两座岛屿的坐标点保存在两个集合中。这一步,我们很容易使用深度优先搜索实现。
第二步,以其中一个岛屿为基础,向外填海造陆,直到与另一座岛屿相切,这时,我们就可以记录用了多少圈,从而找到最短的桥的长度。这一步,我们使用宽度优先搜索。
我们将两步写成功能函数,实现岛屿搜寻通过递归的深度优先搜索,对于填海造陆的过程,使用队列进行逐点遍历,每个点不仅包含位置信息,还需要包含深度信息,也就是当前已经扩充到了第几圈。
以下几点需要留意:
- 获取周围点的坐标时,及时判断点的位置是否合法;
- 使用集合记录遍历过的位置,避免重复的计算开销;
- 递归调用时注意返回值的更新;
class Solution:
def get_islands(self, A):
def dfs(r, c, res:set):
if (r, c) not in seen and 0 <= r < len(A) and 0 <= c < len(A[0]) and A[r][c]:
res.add((r, c))
seen.add((r, c))
for nr, nc in [(r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)]:
dfs(nr, nc, res)
return res
islands = []
seen = set()
for r in range(len(A)):
for c in range(len(A[0])):
if (r, c) not in seen and A[r][c]:
islands.append(dfs(r, c, set()))
seen.add((r, c))
return islands
def shortestBridge(self, A):
R, C = len(A), len(A[0])
def neighbors(r, c):
for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc
island_1, island_2 = self.get_islands(A)
queue = [(node, 0) for node in island_1]
done = set(island_1)
while queue:
location, depth = queue.pop(0)
if location in island_2:
return depth-1
for nei in neighbors(*location):
if nei not in done:
queue.append((nei, depth+1))
done.add(nei)
s = Solution()
A = [[1, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0],
]
# print(s.get_islands(A))
print(s.shortestBridge(A))
如有疑问或建议,欢迎评论区留言~
有关更多力扣中等题的python解决方案,请移步力扣中等题解析
网友评论