AOJ 1281 The Morning after Halloween

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1281

解法

この問題はやるだけなんですが，TLEとMLEをうまく回避するのが大切な問題です．定数倍遅くなりそうな部分はできるだけ排除していく必要があります．
基本BFSをやっていくだけなのですが，最短距離を short で持つようにするとMLEが防げます．
遷移する部分は，とりあえず3つ文字があると仮定した 5^3 のループ（動かない＋4方向に動く）を書いて，適宜つじつまを合わせる実装が楽だと思います．
移動先が壁かどうかの判定を，面倒だからと一番深いループの位置でやるとTLEするので，各文字の遷移先を決めるループごとに枝刈りしないといけません．

あとは変なことを書かなければぎりぎり通ると思います（白目）．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

constexpr int dx[5] = {0, 0, 1, 0, -1};
constexpr int dy[5] = {0, 1, 0, -1, 0};

short d[256][256][256];

void init() {
    for(int i = 0; i < 256; ++i) {
        for(int j = 0; j < 256; ++j) {
            for(int k = 0; k < 256; ++k) {
                d[i][j][k] = 10000;
            }
        }
    }
}

bool move_check(int prev1, int to1, int prev2, int to2) {
    return to1 != to2 && (prev1 != to2 || prev2 != to1);
}

int main() {
    int w, h, n;
    while(cin >> w >> h >> n, n) {
        init();
        vector<string> c(h);
        vector<pii> cs1, cs2;
        cin.ignore(1000, '\n');
        for(int i = 0; i < h; ++i) {
            getline(cin, c[i]);
            for(int j = 0; j < w; ++j) {
                if('a' <= c[i][j] && c[i][j] <= 'z') {
                    cs1.emplace_back(c[i][j], i * w + j);
                }
                if('A' <= c[i][j] && c[i][j] <= 'Z') {
                    cs2.emplace_back(c[i][j], i * w + j);
                }
            }
        }
        sort(begin(cs1), end(cs1));
        sort(begin(cs2), end(cs2));
        array<int, 3> s = {255, 255, 255}, g = {255, 255, 255};
        for(int i = 0; i < n; ++i) {
            s[i] = cs1[i].second;
            g[i] = cs2[i].second;
        }

        queue<pair<array<int, 3>, short>> que;
        d[s[0]][s[1]][s[2]] = 0;
        que.emplace(s, 0);
        int res = 0;
        while(!que.empty()) {
            auto now = que.front().first;
            auto cost = que.front().second;
            que.pop();
            if(now == g) {
                res = cost;
                break;
            }
            for(int i = 0; i < 5; ++i) {
                int ny0 = now[0] / w + dy[i], nx0 = (now[0] % w) + dx[i];
                if(c[ny0][nx0] == '#') {
                    continue;
                }
                for(int j = 0; j < 5; ++j) {
                    int ny1 = now[1] / w + dy[j], nx1 = (now[1] % w) + dx[j];
                    if(n >= 2 && c[ny1][nx1] == '#') {
                        continue;
                    }
                    for(int k = 0; k < 5; ++k) {
                        int ny2 = now[2] / w + dy[k], nx2 = (now[2] % w) + dx[k];
                        if(n == 3 && c[ny2][nx2] == '#') {
                            continue;
                        }
                        array<int, 3> nxt = {ny0 * w + nx0,
                                             (n >= 2 ? ny1 * w + nx1 : 255),
                                             (n == 3 ? ny2 * w + nx2 : 255)};
                        bool move_ok = true;
                        for(int l = 0; n != 1 && l < n; ++l) {
                            move_ok &= move_check(now[l], nxt[l], now[(l + 1) % n], nxt[(l + 1) % n]);
                        }
                        if(move_ok && d[nxt[0]][nxt[1]][nxt[2]] == 10000) {
                            d[nxt[0]][nxt[1]][nxt[2]] = cost + 1;
                            que.emplace(nxt, cost + 1);
                        }
                    }
                }
            }
        }
        cout << res << endl;
    }
}

感想

まあ，最初サボりすぎてTLE食らったんですけどね．実装はきれいに書けたほうだと思う．（速度が早いとは言ってない）
ちなみに 5.50 s / 8.00 s です．あぶねえな．
ケースによるけど，n が小さいならループを回さないようにしたほうが早くはなると思う．でも全部 n == 3 だと意味ないからそういうふうには書かなかった．

A* とか両側探索だと多少早いのかな？