在Python中找到距离水最远的土地的程序

假设我们有一个二进制矩阵，其中0表示水，1表示陆地。现在我们要找到距离水最远的陆地，并最终返回距离。

因此，如果输入如下：

1	1	1	1
1	1	0	1
1	1	1	1
0	0	1	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
• while q不为空，do
  • （r，c）：q的左侧元素，然后从q中删除
  • 对于在 [(r – 1, c)，(r + 1, c)，(r，c + 1)，(r，c – 1)] 中的每个成对物品（x，y），执行以下操作
    • 如果x和y在矩阵的范围内且A [x，y]为1，则
    • A [x，y]：= 0
    • 距离 [x，y]：= 距离 [r，c] +1
    • 在q末尾插入（x，y）
• res：包含每行最大元素的列表
• 返回res的最大值

更多Python相关文章，请阅读：Python 教程

示例（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