Gridgedge [Aizu Competitive Programming Camp 2018 Day 2 D]

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day2/problems/D

前提知識

• ダイクストラ

考察過程

1. ダイクストラしながら経路数も数える例のやつ？
2. ダイクストラしながら、新記録更新したら経路数も更新する

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#ACPC2018Day2/3149583

ダイクストラをする。
(x,y)から(xx,yy)への遷移を考えるときに

• dst[y][x] + 1 ＜ dst[yy][xx]であれば、dp[yy][xx] = dp[y][x]とする
• dst[y][x] + 1 = dst[yy][xx]であれば、dp[yy][xx] += dp[y][x]とする

という処理を加えるだけ。

int W, H, ax, ay, bx, by;
int dst[505][505], vis[505][505]; mint dp[505][505];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> W >> H >> ax >> ay >> bx >> by;

    rep(y, 0, H) rep(x, 0, W) dst[y][x] = inf;
    min_priority_queue<pair<int, int>> que;

    dst[ay][ax] = 0;
    dp[ay][ax] = 1;
    que.push({ 0, ay * 1010 + ax });
    while (!que.empty()) {
        auto q = que.top(); que.pop();

        int x = q.second % 1010;
        int y = q.second / 1010;
        int c = q.first;

        if (vis[y][x]) continue;
        vis[y][x] = 1;

        if (y == by and x == bx) {
            cout << c << " " << dp[y][x] << endl;
            return;
        }

        vector<pair<int, int>> nxt;
        rep(d, 0, 4) nxt.push_back({ x + dx[d], y + dy[d] });
        nxt.push_back({ 0, y });
        nxt.push_back({ W - 1, y });
        nxt.push_back({ x, 0 });
        nxt.push_back({ x, H - 1 });

        fore(p, nxt) {
            int xx, yy;
            tie(xx, yy) = p;

            if (xx < 0 or W <= xx or yy < 0 or H <= yy) continue;

            if (c + 1 < dst[yy][xx]) {
                dst[yy][xx] = c + 1;
                dp[yy][xx] = dp[y][x];
                que.push({ c + 1, yy * 1010 + xx });
            }
            else if (c + 1 == dst[yy][xx]) dp[yy][xx] += dp[y][x];
        }
    }
}