Python程式：查詢距水域最遠陸地的程式

假設我們有一個二進位制矩陣，其中0代表水，1代表陸地。現在我們需要找到距水域曼哈頓距離最遠的陸地，並最終返回該距離。

因此，如果輸入如下所示：

1111
1101
1111
0011

則輸出將為3，因為[0,0]單元格與水域的曼哈頓距離為3。

為了解決這個問題，我們將遵循以下步驟：

  • 如果A為空，則
    • 返回0
  • R := 矩陣的行數，C := 矩陣的列數
  • distance := 一個 R x C 階矩陣，並填充0
  • q := 一個雙端佇列，包含一些 (r, c) 對，其中 r 和 c 是矩陣的行和列索引，矩陣[r, c] 為 0
  • 如果q的大小為0或R * C，則
    • 返回-1
  • 當q不為空時，執行以下操作：
    • (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
        • distance[x, y] := distance[r, c] + 1
        • 將(x, y)插入到q的末尾
  • 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

更新於：2020年12月12日

瀏覽量：137

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告