Try   HackMD
tags: APCS

d378-最小路徑

題目連結: d378

題目解析

老鼠在地圖的左上角 (0, 0),只能向右或向下移動,最終要到達右下角 (N-1, M-1)。每走一格都會消耗體力值,消耗的體力值等於該格的數字。題目要求我們找到從起點到終點的所有可能路徑中,體力消耗最少的那條路徑,並輸出其總體力消耗值。

解題方向

這個問題的解題關鍵在於使用動態規劃:

  1. 狀態定義:
    • 定義一個二維陣列 route,其中 route[i][j] 表示從左上角 (0, 0) 到達該格 (i, j) 的最小體力消耗值。
  2. 狀態轉移:
    • 如果老鼠來自左邊的格子 (i, j-1),則 route[i][j] = route[i][j-1] + grid[i][j]
    • 如果老鼠來自上面的格子 (i-1, j),則 route[i][j] = route[i-1][j] + grid[i][j]
    • route[i][j] = min(route[i-1][j], route[i][j-1]) + grid[i][j],這表示老鼠應該選擇從體力消耗較小的那條路徑來到 (i, j)
  3. 初始化:
    • 對於第一行的每一個格子,只能從左邊的格子移動過來,因此 route[0][j] = route[0][j-1] + grid[0][j]
    • 對於第一列的每一個格子,只能從上面的格子移動過來,因此 route[i][0] = route[i-1][0] + grid[i][0]
  4. 結果輸出:
    • 最終結果是 route[N-1][M-1],即從 (0, 0) 到達 (N-1, M-1) 的最小體力消耗值。

完整程式碼

case = 1 while True: try: # 讀取 N 和 M N, M = map(int, input().split()) # 讀取地圖->grid,是原始地圖 grid = [] for i in range(N): row = list(map(int, input().split())) grid.append(row) # 初始化 route ,是一個「累計」的陣列 route = [[0 for j in range(M)] for i in range(N)] # 初始化第一行和第一列的邊界條件 route[0][0] = grid[0][0] # 起點 # 對於第一列的每一個格子,只能從上面的格子移動過來 for i in range(1, N): route[i][0] = route[i-1][0] + grid[i][0] # 對於第一行的每一個格子,只能從左邊的格子移動過來 for j in range(1, M): route[0][j] = route[0][j-1] + grid[0][j] # 動態規劃計算最小體力消耗 for i in range(1, N): for j in range(1, M): route[i][j] = min(route[i-1][j], route[i][j-1]) + grid[i][j] # 輸出結果 print("Case #%d :\n%d" % (case, route[N-1][M-1])) case += 1 except: break