Python 中迷宮矩陣的最小逃脫步數

假設我們有一個二進位制矩陣，其中 0 表示空單元格，1 表示牆壁。如果我們從左上角 (0, 0) 開始，我們需要找到到達右下角 (R-1, C-1) 所需的最少單元格數。這裡 R 是行數，C 是列數。如果我們找不到任何答案，則返回 -1。

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

那麼輸出將是 8，因為我們可以選擇如下路徑：

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

• R := 行數
• C := 列數
• q := 一個空的列表，如果 matrix[0, 0] 為 0，則最初插入 (0, 0, 1)
• matrix[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，執行以下操作：
    • 如果 0 <= x < R 且 0 <= y < C 並且 matrix[x, y] 等於 0，則
      • matrix[x, y] := 1
      • 在 q 的末尾插入三元組 (x, y, d + 1)
• 返回 -1

示例

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

def solve(matrix):
   R, C = len(matrix), len(matrix[0])
   q = [(0, 0, 1)] if not matrix[0][0] else []
   matrix[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 matrix[x][y] == 0:
            matrix[x][y] = 1
            q.append((x, y, d + 1))
   return -1

matrix = [
   [0, 0, 0, 1, 0],
   [0, 0, 1, 1, 0],
   [0, 0, 0, 1, 1],
   [1, 1, 0, 0, 0]
]
print(solve(matrix))

輸入

[
[0, 0, 0, 1, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 1],
[1, 1, 0, 0, 0]
]

輸出

8

Arnab Chakraborty

更新於: 2021-10-18

929 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習