AtCoder Regular Contest 019 C - 最後の森

問題

　縦 $R$ 行、横 $C$ 列のマス目で構成されているマップについて各マスは

平地……平地のマスは自由に通行できる。
木……木のあるマスは通行できない。
強敵のいるマス……凶暴な強敵のいるマスである。後述の条件を満たさなければ通行できない。
プレイヤーの村……プレイヤーの初期位置である。このマスは自由に通行できる。
ほこら……伝説の剣 Link-Cut Sword があるほこらである。このマスは自由に通行できる。
魔王の城……魔王の城があるマスである。このマスは自由に通行できる。

　のいずれかとなっている。村から出発し、ほこらを通って魔王の城に行くことを考える。強敵は一度倒すと消滅しそのマスは平地と同じとなる。倒す強敵の数が $K$ 以下となるように進むときの最短経路長を求めよ。

解法

　あるマス $(i, j)$ へ倒す強敵の数が $k$ となるように進んだときの最短経路を、出発点として村、ほこら、城の3つを選んだ場合についてそれぞれ幅優先探索で求める。

　全てのマスについて村からそのマス、そのマスからほこら、ほこらからそのマス、そのマスから城という経路についてコストを計算し、一番小さいものが答えとなる。

　調べるマスに敵がいる場合は注意が必要であり、3回同じ敵を数えることになるのでそのマスから城へ行くときの余裕分は+2される。

反省

　3時間3分(9WA)でAC。きつかった……。

　最初は村からほこら、ほこらから城へと2回ダイクストラをやるだけかなと思っていくらか実装していたが、どうも一つだけサンプルが合わない。いろいろ考えていると、

6 4 2
S..T
.TET
.TCT
..ET
..ET
TTGT

　のようなケースでダメだということに気が付いた。つまりSからCへ戦闘回数が2回以下で行くときの最短経路は、Cの上にあるEを2回踏むことで達成できてしまうが、それでは最終的な経路は長くなってしまう。ダイクストラでは途中の敵の遭遇具合を管理できないのでこの方法ではうまくいかないと悟ったのが1時間30分ごろ。

　おそらく深さ優先探索的なことをしていくのだろうと思いつつわからなかったので解説スライドを読んだら全然考えてもないことばかりが書いてあった。

　苦しみつつ実装をしたところ、ダイクストラのときにダメだったサンプルがやはり合わない。調べるマスに敵がいる場合についてマスから城へ行くときの余裕分に1しか足していなかったのが原因だったようだ。村からそのマスで1回、ほこらへと往復するから2回で、同じ敵を3回数えた計算になることがわかっていなかった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll R, C, K;
vector<string> s;
enum {
    START, CENTER, GOAL, NUM
};

constexpr ll dx[] = { 0, 1, 0, -1 };
constexpr ll dy[] = { 1, 0, -1, 0 };
bool isOK(ll x, ll y) {
    return (0 <= x && x < C && 0 <= y && y < R && s[y][x] != 'T');
};

void bfs(ll sx, ll sy, vector<vector<vector<ll>>>& cost) {
    queue<tuple<ll, ll, ll>> q;
    q.push(make_tuple(sx, sy, 0));

    while (!q.empty()) {
        ll x, y, k;
        tie(x, y, k) = q.front();
        q.pop();

        for (ll i = 0; i < 4; i++) {
            ll nx = x + dx[i];
            ll ny = y + dy[i];
            if (!isOK(nx, ny)) {
                continue;
            }
            ll nk = k + (s[ny][nx] == 'E');
            if (nk > K) {
                continue;
            }
            ll nc = cost[y][x][k] + 1;
            if (nc < cost[ny][nx][nk]) {
                cost[ny][nx][nk] = nc;
                q.push(make_tuple(nx, ny, nk));
            }
        }
    }
}

int main() {
    cin >> R >> C >> K;
    s.resize(R);

    vector<ll> pos_x(NUM), pos_y(NUM);

    for (ll i = 0; i < R; i++) {
        cin >> s[i];
        for (ll j = 0; j < C; j++) {
            if (s[i][j] == 'S') {
                pos_x[START] = j;
                pos_y[START] = i;
            } else if (s[i][j] == 'C') {
                pos_x[CENTER] = j;
                pos_y[CENTER] = i;
            } else if (s[i][j] == 'G') {
                pos_x[GOAL] = j;
                pos_y[GOAL] = i;
            }
        }
    }

    vector<vector<vector<vector<ll>>>> cost(NUM, vector<vector<vector<ll>>>(R, vector<vector<ll>>(C, vector<ll>(K + 1, INT_MAX))));

    for (ll i = 0; i < NUM; i++) {
        cost[i][pos_y[i]][pos_x[i]][0] = 0;
        bfs(pos_x[i], pos_y[i], cost[i]);
    }

    ll ans = INT_MAX;
    for (ll i = 0; i < R; i++) {
        for (ll j = 0; j < C; j++) {
            if (s[i][j] == 'T') {
                continue;
            }

            //戦闘回数k回以下で行けるときk+1回以下でも行ける
            for (ll n = 0; n < NUM; n++) {
                for (ll k = 0; k < K; k++) {
                    cost[n][i][j][k + 1] = min(cost[n][i][j][k + 1], cost[n][i][j][k]);
                }
            }

            //sから(i, j)へk1回の戦闘で行き、(i, j)からcへk2回の戦闘で行って戻ってきて、(i, j)からgへ残りの戦闘回数で行く
            for (ll k1 = 0; k1 <= K; k1++) {
                for (ll k2 = 0; k2 <= K; k2++) {
                    ll k3 = K - k1 - k2;
                    if (s[i][j] == 'E') {
                        k3 += 2;
                    }
                    if (k3 < 0 || K < k3) {
                        continue;
                    }
                    ans = min(ans, cost[0][i][j][k1] + 2 * cost[1][i][j][k2] + cost[2][i][j][k3]);
                }
            }
        }
    }

    cout << (ans == INT_MAX ? -1 : ans) << endl;
}