#include #include #include #include #include using namespace std; #define REP(i,n) for(int i = 0; i < static_cast(n); ++i) #define REP2(i,s,n) for(int i = (s); i < static_cast(n); ++i) enum Direc { U, R, D, L }; // Up, Right, Down, Left string d2s(Direc d) { switch (d) { case U: return "U"; case D: return "D"; case L: return "L"; case R: return "R"; } assert(false); } struct Node { int r, c; Direc d; Node() {} Node(int r_, int c_, Direc d_): r(r_), c(c_), d(d_) {} bool operator==(const Node &n) { return r == n.r && c == n.c && d == n.d; } friend ostream &operator<<(ostream &os, const Node &n) { return os << "(" << n.r << "," << n.c << ";" << d2s(n.d) << ")"; } }; const size_t W = 64; const size_t H = 16; bool visited1[H][W][4]; bool visited2[H][W][4][H][W][4]; class Karakuri { public: Karakuri(int w, int h); void input(); void calc1(); void calc2(); void output(); void print(); private: int width; vector rmap; Node start, goal; bool reachable, returnable; char next(int r, int c, Direc d); void go_next(int &r, int &c, Direc d); void go_through(Node &n); Direc rev(Direc d); Node rev(Node n); Direc clock(Direc d); vector onright(Node n, bool on_left = false); inline vector onleft(const Node &n); bool rctrav(Node n); bool rntrav(Node f, Node b); }; /* * main */ int main() { int w, h; while (scanf("%d%d\n", &w, &h), w) { Karakuri kd(w, h); kd.input(); kd.calc1(); kd.calc2(); //kd.print(); kd.output(); } } // --- implementation of Karakuri ----------------------------------------------------------------- /* * public functions */ Karakuri::Karakuri(int w, int h): width(w), rmap(h), reachable(false), returnable(false) {} void Karakuri::input() { REP(i, rmap.size()) { REP(j, width) { char ch = getchar(); if (ch == 'K') { start.r = i; start.c = j; } if (ch == 'M') { goal.r = i; goal.c = j; } rmap[i].push_back(ch); } getchar(); // '\n' } // determine the directions int d; for (d = 0; next(start.r, start.c, (Direc)d) == '#'; ++d); assert(d < 4); start.d = (Direc)d; for (d = 0; next(goal.r, goal.c, (Direc)d) == '#'; ++d); assert(d < 4); goal.d = (Direc)d; go_through(goal); } void Karakuri::calc1() { REP(i,H) REP(j,W) REP(k,4) { visited1[i][j][k] = false; } reachable = rctrav(start); } void Karakuri::calc2() { if (!reachable) return; REP(i1,H) REP(j1,W) REP(k1,4) REP(i2,H) REP(j2,W) REP(k2,4) { visited2[i1][j1][k1][i2][j2][k2] = false; } vector bs; REP(i,4) { if ((Direc)i == start.d) continue; Node n = start; n.d = (Direc)i; bs.push_back(n); } returnable = false; REP(i,3) { if (rntrav(start, bs[i])) { returnable = true; break; } } } void Karakuri::output() { if (!reachable) { puts("He cannot bring tea to his master."); } else if (!returnable) { puts("He cannot return to the kitchen."); } else { puts("He can accomplish his mission."); } } void Karakuri::print() { cout << "kitchen: " << start << endl; cout << "master': " << goal << endl; REP(i, rmap.size()) { cout << rmap[i] << endl; } } /* * private functions */ char Karakuri::next(int r, int c, Direc d) { switch (d) { case U: return rmap[r-1][c]; case D: return rmap[r+1][c]; case L: return rmap[r][c-1]; case R: return rmap[r][c+1]; } assert(false); } void Karakuri::go_next(int &r, int &c, Direc d) { switch (d) { case U: --r; return; case D: ++r; return; case L: --c; return; case R: ++c; return; } assert(false); } void Karakuri::go_through(Node &n) { while (next(n.r, n.c, n.d) != '#') { go_next(n.r, n.c, n.d); } } // rotate clockwise Direc Karakuri::clock(Direc d) { return (Direc)(((int)d + 1) % 4); } Direc Karakuri::rev(Direc d) { return clock(clock(d)); } Node Karakuri::rev(Node n) { n.d = rev(n.d); return n; } // set of nodes which has n on the right vector Karakuri::onright(Node n, bool on_left) { vector ret; n = rev(n); Direc r = clock(n.d); if (on_left) { r = rev(r); } for (;;) { if (next(n.r, n.c, r) == '#') { ret.push_back(Node(n.r, n.c, r)); } if (next(n.r, n.c, n.d) == '#') { break; } go_next(n.r, n.c, n.d); } return ret; } vector Karakuri::onleft(const Node &n) { return onright(n, true); } bool Karakuri::rctrav(Node n) { go_through(n); if (visited1[n.r][n.c][n.d]) { return false; } visited1[n.r][n.c][n.d] = true; if (rmap[n.r][n.c] == 'M') { return true; } // turn right n.d = clock(n.d); if (rctrav(n)) { return true; } // turn left n.d = rev(n.d); if (rctrav(n)) { return true; } return false; } bool Karakuri::rntrav(Node f, Node b) { go_through(f); if (visited2[f.r][f.c][f.d][b.r][b.c][b.d]) { return false; } visited2[f.r][f.c][f.d][b.r][b.c][b.d] = true; if (rmap[f.r][f.c] == 'M' && b == goal) { return true; } // turn right f.d = clock(f.d); vector nb = onleft(b); REP(i, nb.size()) { if (rntrav(f, nb[i])) { return true; } } // turn left f.d = rev(f.d); nb = onright(b); REP(i, nb.size()) { if (rntrav(f, nb[i])) { return true; } } return false; }