【題解】TIOJ 1196 . 小豬Piggy

#include <iostream>
using namespace std;

int n, a[10][10], dp[10][10];
char c;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> c;
            if (c-'0'>=0 && c-'0'<=9) a[i][j] = c-'0';
            else a[i][j] = -1;
        }
    }
    a[0][0] = 0;
    a[n-1][n-1] = 0;
    dp[0][0] = 0;
    for (int i = 1; i < n; i++){
        if (dp[i-1][0] == -1 || a[i][0] == -1) dp[i][0] = -1;
        else dp[i][0] = dp[i-1][0] + a[i][0];
        if (dp[0][i-1] == -1 || a[0][i] == -1) dp[0][i] = -1;
        else dp[0][i] = dp[0][i-1] + a[0][i];
    }
    for (int i = 1; i < n; i++){
        for (int j = 1; j < n; j++){
            if (a[i][j] == -1 || (dp[i-1][j] == -1 && dp[i][j-1] == -1)){
                dp[i][j] = -1;
                continue;
            }
            if (dp[i][j-1] != -1) dp[i][j] = max(dp[i][j], dp[i][j-1]+a[i][j]);
            if (dp[i-1][j] != -1) dp[i][j] = max(dp[i][j], dp[i-1][j]+a[i][j]);
        }
    }
    if (dp[n-1][n-1] == -1) cout << "X\n";
    else cout << dp[n-1][n-1] << "\n";
}