AOJ 2017: からくり人形 / Karakuri Doll

,

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

solution

全探索。少し重め実装を丁寧にやるだけ。$O(H^2W^2)$。

$H \le 16, \; W \le 64$で人形の向き$d = 4$を入れても$(H \cdot W \cdot d)^2 \approx 1.6 \times 10^7$と小さい。 行きと帰りを両方同時に探索することを考える。 帰りは命令列の末尾から実行するので単純には無理だが、帰りは最終的に始点$K$で止まることが分かっているので後ろ向きに歩かせるようにする。

注意点としては、

  • 後ろ向きに歩いていって止まる位置は左右に壁がある位置だが、$0$を含む複数の候補がありうる
  • 帰り方向での候補が$0$でも、行きだけなら可能な場合があること
  • 帰りでも出発の際は向きが固定なので、終了判定のときこれを忘れない

implementation

#include <cstdio>
#include <queue>
#include <set>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

int solve(int h, int w, vector<vector<char> > const & f) {
    // prepare
    const int dy[4] = { 0, -1, 0, 1 };
    const int dx[4] = { 1, 0, -1, 0 };
    auto r = [](int d) { return (d + 1) % 4; };
    auto l = [](int d) { return (d - 1 + 4) % 4; };
    int start_y, start_x, goal_y, goal_x;
    repeat (y, h) {
        repeat (x, w) {
            if (f[y][x] == 'K') {
                start_y = y;
                start_x = x;
            }
            if (f[y][x] == 'M') {
                goal_y = y;
                goal_x = x;
            }
        }
    }
    int start_d;
    repeat (d, 4) {
        int y = start_y + dy[d];
        int x = start_x + dx[d];
        if (f[y][x] != '#') {
            start_d = d;
        }
    }
    int goal_d;
    repeat (d, 4) {
        int y = goal_y + dy[d];
        int x = goal_x + dx[d];
        if (f[y][x] != '#') {
            goal_d = d;
        }
    }
    // search
    set<tuple<int, int, int, int, int, int> > used;
    queue<tuple<int, int, int, int, int, int> > que;
    repeat (d, 4) {
        auto it = make_tuple(start_y, start_x, start_d, start_y, start_x, d);
        used.insert(it);
        que.push(it);
    }
    int result = 0;
    auto push = [&](int y1, int x1, int d1, int y2, int x2, int d2, char prev_d2) {
        if (y1 == goal_y and x1 == goal_x) {
            setmax(result, 1);
            if (y2 == goal_y and x2 == goal_x and prev_d2 == goal_d) {
                setmax(result, 2);
            }
        }
        auto it = make_tuple(y1, x1, d1, y2, x2, d2);
        if (not used.count(it)) {
            used.insert(it);
            que.push(it);
        }
    };
    while (not que.empty() and result != 2) {
        int y1, x1, d1, y2, x2, d2;
        tie(y1, x1, d1, y2, x2, d2) = que.front();
        que.pop();
        while (f[y1 + dy[d1]][x1 + dx[d1]] != '#') {
            y1 += dy[d1];
            x1 += dx[d1];
        }
        push(y1, x1, r(d1), -1, -1, -1, -1);
        push(y1, x1, l(d1), -1, -1, -1, -1);
        if (d2 == -1) continue;
        while (f[y2][x2] != '#') {
            if (f[y2 + dy[r(d2)]][x2 + dx[r(d2)]] == '#') {
                push(y1, x1, r(d1), y2, x2, r(d2), d2);
            }
            if (f[y2 + dy[l(d2)]][x2 + dx[l(d2)]] == '#') {
                push(y1, x1, l(d1), y2, x2, l(d2), d2);
            }
            y2 -= dy[d2];
            x2 -= dx[d2];
        }
    }
    return result;
}

int main() {
    while (true) {
        int w, h; scanf("%d%d", &w, &h);
        if (w == 0 and h == 0) break;
        auto f = vectors(h, w, char());
        repeat (y, h) repeat (x, w) scanf(" %c", &f[y][x]);
        int result = solve(h, w, f);
        printf("%s\n",
                result == 0 ? "He cannot bring tea to his master." :
                result == 1 ? "He cannot return to the kitchen." :
                              "He can accomplish his mission.");
    }
    return 0;
}