Python程序:查找岛屿之间最短桥的距离
假设我们有一个二进制矩阵,其中 0 代表水,1 代表陆地。一个岛屿是一组在 4 个方向上连接的 1。岛屿要么被 0(水)包围,要么被边缘包围。我们必须找到连接两个岛屿的最短桥的长度。
所以,如果输入是这样的
0 | 0 | 1 |
1 | 0 | 1 |
1 | 0 | 0 |
那么输出将是 1。这将连接 (1,0) 到 (1,2) 点。
为了解决这个问题,我们将遵循以下步骤:
row := 矩阵的行数
col := 矩阵的列数
定义一个函数 dfs()。它将接收 i、j、s 作为参数
如果 (i, j) 在 s 中,则
返回
如果 mat[i, j] 等于 0,则
返回
将 (i, j) 插入 s
如果 i - 1 >= 0,则
dfs(i - 1, j, s)
如果 i + 1 < row,则
dfs(i + 1, j, s)
如果 j - 1 >= 0,则
dfs(i, j - 1, s)
如果 j + 1 < col,则
dfs(i, j + 1, s)
从主方法执行以下操作:
seen := 一个新的集合
对于 i 从 0 到 row 的范围,执行
如果 seen 的大小 > 0,则
退出循环
对于 j 从 0 到 col 的范围,执行
如果 mat[i, j] 等于 1,则
dfs(i, j, seen)
退出循环
q := 一个双端队列
对于 seen 中的每个陆地,执行
(i, j) := 陆地
如果 i - 1 >= 0 且 mat[i - 1, j] 等于 0,则
将 (i - 1, j, 1) 插入 q 的末尾
如果 i + 1 < row 且 mat[i + 1, j] 等于 0,则
将 (i + 1, j, 1) 插入 q 的末尾
如果 j - 1 >= 0 且 mat[i, j - 1] 等于 0,则
将 (i, j - 1, 1) 插入 q 的末尾
如果 j + 1 < col 且 mat[i, j + 1] 等于 0,则
将 (i, j + 1, 1) 插入 q 的末尾
当 q 的大小 > 0 时,执行
(i, j, dist) := q 的左边的项,并从 q 的左边删除该项
如果 (i, j) 在 seen 中,则
进入下一次迭代
将 (i, j) 标记为 seen
如果 mat[i, j] 等于 1,则
返回 dist - 1
如果 i - 1 >= 0,则
将 (i - 1, j, dist + 1) 插入 q 的末尾
如果 i + 1 < row 不为零,则
将 (i + 1, j, dist + 1) 插入 q 的末尾
如果 j - 1 >= 0,则
将 (i, j - 1, dist + 1) 插入 q 的末尾
如果 j + 1 < col 不为零,则
将 (i, j + 1, dist + 1) 插入 q 的末尾
示例
让我们看看以下实现以获得更好的理解:
import collections class Solution: def solve(self, mat): row = len(mat) col = len(mat[0]) def dfs(i, j, s): if (i, j) in s: return if mat[i][j] == 0: return s.add((i, j)) if i - 1 >= 0: dfs(i - 1, j, s) if i + 1 < row: dfs(i + 1, j, s) if j - 1 >= 0: dfs(i, j - 1, s) if j + 1 < col: dfs(i, j + 1, s) seen = set() for i in range(row): if len(seen) > 0: break for j in range(col): if mat[i][j] == 1: dfs(i, j, seen) break q = collections.deque() for land in seen: i, j = land if i - 1 >= 0 and mat[i - 1][j] == 0: q.append((i - 1, j, 1)) if i + 1 < row and mat[i + 1][j] == 0: q.append((i + 1, j, 1)) if j - 1 >= 0 and mat[i][j - 1] == 0: q.append((i, j - 1, 1)) if j + 1 < col and mat[i][j + 1] == 0: q.append((i, j + 1, 1)) while len(q) > 0: i, j, dist = q.popleft() if (i, j) in seen: continue seen.add((i, j)) if mat[i][j] == 1: return dist - 1 if i - 1 >= 0: q.append((i - 1, j, dist + 1)) if i + 1 < row: q.append((i + 1, j, dist + 1)) if j - 1 >= 0: q.append((i, j - 1, dist + 1)) if j + 1 < col: q.append((i, j + 1, dist + 1)) ob = Solution() matrix = [ [0, 0, 1], [1, 0, 1], [1, 0, 0], ] print(ob.solve(matrix))
输入
[ [0, 0, 1], [1, 0, 1], [1, 0, 0], ]
输出
1