AtCoder ABC 037 D

June 23, 2020

解説と異なる方針で解いたのでメモ。

D - 経路

条件を満たす経路の総数を求める。DPで解けるけれど、DPの更新順序を考えないといけない。解説のようにメモ化再帰で解けば、順序を考えずに済む。この問題では、最も小さい値をもつマスから順に更新していく。この順序で計算していけば、一度計算の済んだマスについてもう一度経路数が更新されるということはない。

 
using P = pair<i64, i64>;
using T = pair<i64, P>;

i64 G[1000][1000];
mint dp[1000][1000];

const i64 dy[4] = {-1, 0, 1, 0};
const i64 dx[4] = {0, -1, 0, 1};

int main() {
    i64 H, W; cin >> H >> W;
    vector<T> vals;
    REP(y, H) REP(x, W) {
        cin >> G[y][x];
        vals.pb({G[y][x], {y, x}});
    }
    sort(vals.begin(), vals.end());

    auto inside = [&](i64 y, i64 x) {
        return (0 <= y && y < H && 0 <= x && x < W);
    };

    REP(i, H * W) {
        T t = vals[i];
        i64 v = t.first;
        auto [y, x] = t.second;
        REP(j, 4) {
            i64 ny = y + dy[j];
            i64 nx = x + dx[j];
            if (inside(ny, nx) && G[ny][nx] > v) {
                dp[ny][nx] += dp[y][x] + 1;
            }
        }
    }

    mint cnt = H * W;
    REP(y, H) REP(x, W) cnt += dp[y][x];
    cout << cnt << endl;

    return 0;
}