Python中寻找离水最远陆地的程序
假设我们有一个二进制矩阵，其中0代表水，1代表土地。现在，我们必须找到曼哈顿到水的距离最长的土地，最后返回距离。
所以，如果输入像
那么输出将为3，因为[0,0]单元与水的曼哈顿距离为3。
为了解决这个问题，我们将遵循以下步骤-
如果A为空，则
返回0
R：=矩阵的行数，C：=矩阵的列数
距离：=RxC阶的矩阵，并用0填充
q：=具有一些对(r,c)的双头队列，其中r和c是矩阵的行和列索引，其中matrix[r，c]为0
如果q的大小是0或R*C，则
返回-1
当q不为空时，执行
如果x和y在矩阵范围内且A[x，y]为1，则
A[x，y]：=0
distance[x，y]：=距离[r，c]+1
在q的末尾插入(x,y)
(r,c)：=q的左元素，然后从q中删除
对于[[r-1，c），（r+1，c），（r，c+1），(r,c-1)]中的每对(x,y)
res：=包含每行最大元素的列表
返回最大res
范例(Python)
让我们看下面的实现以更好地理解-
from collections import deque
class Solution:
def solve(self, A):
if not A:
return 0
R, C = len(A), len(A[0])
distance = [[0] * C for _ in range(R)]
q = deque((r, c) for r in range(R) for c in range(C) if not A[r][c])
if len(q) in (0, R * C):
return -1
while q:
r, c = q.popleft()
for x, y in [(r - 1, c), (r + 1, c), (r, c + 1), (r, c - 1)]:
if 0 <= x < R and 0 <= y < C and A[x][y]:
A[x][y] = 0
distance[x][y] = distance[r][c] + 1
q.append((x, y))
return max(max(row) for row in distance)
ob = Solution()
matrix = [
[1, 1, 1, 1],
[1, 1, 0, 1],
[1, 1, 1, 1],
[0, 0, 1, 1]
]
print(ob.solve(matrix))输入值
[ [1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1], [0, 0, 1, 1] ]
输出结果
3