###### tags: `APCS`
# **d378－最小路徑**
### **題目連結：** [**d378**](https://zerojudge.tw/ShowProblem?problemid=d378)
### **題目解析**
老鼠在地圖的左上角 (0, 0)，只能向右或向下移動，最終要到達右下角 (N-1, M-1)。每走一格都會消耗體力值，消耗的體力值等於該格的數字。題目要求我們找到從起點到終點的所有可能路徑中，體力消耗最少的那條路徑，並輸出其總體力消耗值。
### **解題方向**
這個問題的解題關鍵在於使用動態規劃：

1. 狀態定義：
* 定義一個二維陣列 `route`，其中 `route[i][j]` 表示從左上角 `(0, 0)` 到達該格 `(i, j)` 的最小體力消耗值。
1. 狀態轉移：
* 如果老鼠來自左邊的格子 `(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)`。
1. 初始化：
* 對於第一行的每一個格子，只能從左邊的格子移動過來，因此 `route[0][j] = route[0][j-1] + grid[0][j]`。
* 對於第一列的每一個格子，只能從上面的格子移動過來，因此 `route[i][0] = route[i-1][0] + grid[i][0]`。
1. 結果輸出：
* 最終結果是 `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