Python程式：找出到達目標的最短路徑

假設我們有一個網格，網格中的單元格包含各種符號，例如'X'、'O'、'*'和'#'，這些符號具有不同的含義。

• '#' 是我們要到達的目標單元格。
• 'O' 是我們可以透過它到達目標單元格的自由單元格。
• '*' 是我們在單元格中的位置。
• 'X' 是一個被阻塞的單元格，我們無法透過它移動。

我們必須找出從我們在網格中的當前位置到達目標單元格所需的步數。如果目標不可達，我們返回-1。網格作為輸入提供給程式。

因此，如果輸入類似於

則輸出將為2

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

• m := 網格的行數
• n := 網格的列數
• 對於 i 從 0 到 m，執行：
  • 對於 j 從 0 到 n，執行：
    • 如果 grid[i, j] 等於 "*"，則：
      • 退出迴圈
    • 否則：
      • 繼續下一次迭代
    • 退出迴圈
• ans := 0
• queue := 一個新的列表，包含整數對 (i, j)
• grid[i, j] := "X"
• 當 queue 不為空時，執行：
  • ans := ans + 1
  • newq := 一個新的列表
  • 對於 queue 中的每個 i, j，執行：
    • 對於 (i-1, j) , (i, j-1) , (i, j+1) , (i+1, j) 中的每個 ii, jj，執行：
      • 如果 0 <= ii < m 且 0 <= jj < n 且 grid[ii, jj] 不等於 "X"，則：
        • 如果 grid[ii, jj] 等於 "#"，則：
          • 返回 ans
        • 將 ii, jj 插入 newq 的末尾
        • grid[ii, jj] := "X"
  • queue := newq
• 返回 -1

示例

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

def solve(grid):
   m, n = len(grid), len(grid[0])
   for i in range(m):
      for j in range(n):
         if grid[i][j] == "*": break
      else: continue
      break
   ans = 0
   queue = [(i, j)]
   grid[i][j] = "X"
   while queue:
      ans += 1
      newq = []
      for i, j in queue:
         for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
            if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
               if grid[ii][jj] == "#": return ans
               newq.append((ii, jj))
               grid[ii][jj] = "X"
      queue = newq
   return -1

print(solve([['X', 'X', 'O', 'X'],['X', 'X', '*', 'X'],['X', '#',
'O', 'X'],['X', 'X', 'X', 'X']]))

輸入

[['X', 'X', 'O', 'X'],
['X', 'X', '*', 'X'],
['X', '#', 'O', 'X'],
['X', 'X', 'X', 'X']]

輸出

2

Arnab Chakraborty

更新於：2021年10月6日

358 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習