在Python中查找岛之间最短桥的距离的程序

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

所以，如果输入像

那么输出将为1。这将把(1,0)连接到(1,2)点。

在线示例

让我们看下面的实现以更好地理解-

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