Python程式：查詢到達右下角所需的最小單元格數量

假設我們有一個二維網格表示迷宮，其中 0 表示空位，1 表示牆壁。我們從網格 [0, 0] 開始，需要找到到達網格右下角所需的最小正方形數量。如果無法到達，則返回 -1。

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

則輸出為 5

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

• R := 網格的行數，C := 網格的列數

• q := [0, 0, 1] 當 A[0, 0] 為 1 時，否則為一個新列表

• A[0, 0] := 1

• 對於 q 中的每個 (r, c, d)，執行以下操作：

  • 如果 (r, c) 與 (R - 1, C - 1) 相同，則

    • 返回 d

  • 
    

    • 對於 [(r + 1, c) ,(r - 1, c) ,(r, c + 1) ,(r, c - 1) ] 中的每個 (x, y)，執行以下操作：

      • 如果 x 在 0 到 R 的範圍內，並且 y 在 0 到 C 的範圍內，並且 A[x, y] 等於 0，則

        • A[x, y] := 1

        • 將 (x, y, d + 1) 插入到 q 的末尾

• 返回 -1

讓我們看看以下實現以更好地理解：

示例

 線上演示

class Solution:
   def solve(self, A):
      R, C = len(A), len(A[0])
      q = [(0, 0, 1)] if not A[0][0] else []
      A[0][0] = 1
      for r, c, d in q:
         if (r, c) == (R − 1, C − 1):
            return d
         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] == 0:
               A[x][y] = 1
               q.append((x, y, d + 1))
      return −1
ob = Solution()
grid = [
   [0, 0, 0],
   [1, 0, 0],
   [1, 0, 0]
]
print(ob.solve(grid))

輸入

grid = [ [0, 0, 0], [1, 0, 0], [1, 0, 0] ]

輸出

5

Arnab Chakraborty

更新時間： 2020年10月21日

168 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始