在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