Python中寻找离水最远陆地的程序

假设我们有一个二进制矩阵，其中0代表水，1代表土地。现在，我们必须找到曼哈顿到水的距离最长的土地，最后返回距离。

所以，如果输入像

那么输出将为3，因为[0,0]单元与水的曼哈顿距离为3。

为了解决这个问题，我们将遵循以下步骤-

• 如果A为空，则

• 返回0

• R：=矩阵的行数，C：=矩阵的列数

• 距离：= R x C阶的矩阵，并用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