【題解】ZeroJudge d378: 最小路徑

題目敘述:https://zerojudge.tw/ShowProblem?problemid=d378
解題想法:

  • 老鼠在地圖上走的時候時,只能往右或下走。
  • dp[i][j]初始值即輸入測資:老鼠走經(i, j)那一格時消耗的體力。
  • Case-I (row-0):只能從左邊那一格走過來。dp[0][j] = dp[0][j-1] + dp[0][j]
  • Case-II (column-0):只能從上面那一格走下來。dp[i][0] = dp[i-1][0] + dp[i][0]
  • Case-III (其它格子):可經由左邊或上方那一格走過來,選擇消耗體力較小的路徑,dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + dp[i][j]
#include <iostream>
using namespace std;

int c = 0, n, m, a[1005][1005];

int main() {
    while (cin >> n >> m){
        c++;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                cin >> a[i][j];
            }
        }
        for (int i = 1; i < n; i++){
            a[i][0] += a[i-1][0];
        }
        for (int j = 1; j < m; j++){
            a[0][j] += a[0][j-1];
        }
        for (int i = 1; i < n; i++){
            for (int j = 1; j < m; j++){
                a[i][j] += min(a[i-1][j], a[i][j-1]);
            }
        }
        cout << "Case #" << c << " :\n" << a[n-1][m-1]<< "\n";
    }
}

Python code (credit: Amy Chou)

T = 1
while True:
    try:
        N, M = map(int, input().split())
        dp = []
        for i in range(N):
            tmp = list(map(int, input().split()))
            dp.append(tmp)
            
        for j in range(1, M):
            dp[0][j] += dp[0][j-1]
            
        for i in range(1, N):
            dp[i][0] += dp[i-1][0]
        
        for i in range(1, N):
            for j in range(1, M):
                dp[i][j] += min(dp[i-1][j], dp[i][j-1])
                
        print(f"Case #{T} :")
        print(dp[N-1][M-1])
        T += 1
    except:
        break
分享本文 Share with friends