【題解】AtCoder ABC 210D – National Railway

#include <iostream>
using namespace std;
 
int h, w, c, a[1005][1005];
long long ans = 1e18, dp[1005][1005];
 
int main() {
    cin >> h >> w >> c;
    for (int i = 1; i <= h; i++){
        for (int j = 1; j <= w; j++){
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= h; i++){
        for (int j = 1; j <= w; j++){
            dp[i][j] = a[i][j];
            if (i > 1){
                ans = min(ans, dp[i-1][j]+c+a[i][j]);
                dp[i][j] = min(dp[i][j], dp[i-1][j]+c);
            }
            if (j > 1){
                ans = min(ans, dp[i][j-1]+c+a[i][j]);
                dp[i][j] = min(dp[i][j], dp[i][j-1]+c);
            }
        }
    }
    for (int i = 1; i <= h; i++){
        for (int j = w; j >= 1; j--){
            dp[i][j] = a[i][j];
            if (i > 1){
                ans = min(ans, dp[i-1][j]+c+a[i][j]);
                dp[i][j] = min(dp[i][j], dp[i-1][j]+c);
            }
            if (j < w){
                ans = min(ans, dp[i][j+1]+c+a[i][j]);
                dp[i][j] = min(dp[i][j], dp[i][j+1]+c);
            }
        }
    }
    cout << ans << "\n";
}