Python程序:查找岛屿之间最短桥的距离


假设我们有一个二进制矩阵,其中 0 代表水,1 代表陆地。一个岛屿是一组在 4 个方向上连接的 1。岛屿要么被 0(水)包围,要么被边缘包围。我们必须找到连接两个岛屿的最短桥的长度。

所以,如果输入是这样的

001
101
100

那么输出将是 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

更新于:2020-12-22

396 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告