CCC 2004 S5 Super Plumber

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4const int inf = 1e9;
    5const long long INF = 1e17; //❄️
    6int main() {
    7    ios::sync_with_stdio(0); cin.tie(0); 
    8    int r, c; cin >> r >> c;
    9    while (true) {
    10        if (r == 0 && c == 0) break;
    11        vector<vector<char>> g(r, vector<char>(c));
    12        for (int i = 0; i < r; i++) {
    13            for (int j = 0; j < c; j++) {
    14                cin >> g[i][j];
    15            }
    16        }
    17        auto calc = [&] (int i, int j) {
    18            if (g[i][j] == '.' || g[i][j] == '*') return 0;
    19            return g[i][j] - '0';
    20        };
    21        vector<int> dp(r, -inf), odp(r, -inf);
    22        odp[r - 1] = calc(r - 1, 0);
    23        for (int i = r - 2; i >= 0; i--) {
    24            if (g[i][0] == '*') break;
    25            odp[i] = odp[i + 1] + calc(i, 0);
    26        }
    27        for (int i = 1; i < c; i++) {
    28            vector<int> cur(r, -inf), down(r, -inf), up(r, -inf); // cur[j] = max coin you get by moving right into column i at row j
    29            for (int j = 0; j < r; j++) {
    30                if (g[j][i] == '*' || odp[j] == -inf) continue;
    31                cur[j] = odp[j] + calc(j, i);
    32            }
    33            for (int j = 0; j < r; j++) {
    34                if (g[j][i] == '*') {
    35                    down[j] = -inf;
    36                    continue;
    37                }
    38                int best = cur[j];
    39                if (j > 0 && down[j - 1] != -inf) {
    40                    best = max(best, down[j - 1] + calc(j, i));
    41                }
    42                down[j] = best;
    43            }
    44            for (int j = r - 1; j >= 0; j--) {
    45                if (g[j][i] == '*') {
    46                    up[j] = -inf;
    47                    continue;
    48                }
    49                int best = cur[j];
    50                if (j < r - 1 && up[j + 1] != -inf) {
    51                    best = max(best, up[j + 1] + calc(j, i));
    52                }
    53                up[j] = best;
    54            }
    55            for (int j = 0; j < r; j++) {
    56                dp[j] = max(down[j], up[j]);
    57            }
    58            swap(odp, dp);
    59        }
    60        cout << odp[r - 1] << '\n';
    61        cin >> r >> c;
    62    }
    63    return 0;
    64}