在Python中找到两个岛屿之间最短桥的程序

假设我们有一个二进制矩阵，其中0代表水，1代表陆地。一个岛屿是四个方向上连接的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 := 一个新集合
对于范围从 0 到行的 i，执行
- 如果 seen 的大小 > 0，则
  - 退出循环
- 对于范围从 0 到列的 j，执行
  - 如果 mat[i，j] 等于 1，则
  - dfs(i，j，seen)
  - 退出循环
q := 一个双向队列
对于 seen 中的每个陆地执行
- (i，j) := land
- 如果 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 的左侧项目，并从左侧删除项目
- 如果 (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))