AOJ 2017: からくり人形 / Karakuri Doll
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;
}