// Karakuri Doll #include #include #include #include #include using namespace std; int DEBUG = 0; enum{ RIGHT = 0, UP = 1, LEFT = 2, DOWN = 3 }; enum{ S_LEFT = 0, S_RIGHT = 1 }; // 左に曲がる = +1 // 右に曲がる = -1 class Automaton { public: vector< int > succ[2]; vector< vector< int > > prev[2]; }; void show( FILE *fp, const vector< int > &b, // 1: wall 0: floor int X, int Y, int start, int goal ) { fprintf( fp, "%d %d\n", X, Y ); for( int y = 0, i = 0; y < Y; y ++ ){ for( int x = 0; x < X; x ++, i ++ ){ if( b[i] ) fprintf( fp, "#" ); else if( i == start ) fprintf( fp, "K" ); else if( i == goal ) fprintf( fp, "M" ); else fprintf( fp, "." ); } fprintf( fp, "\n" ); } fflush( fp ); return; } int create_automaton( const vector< int > &b, // 1: wall 0: floor int X, int Y, int start, int goal, Automaton &a ) { const int n = b.size() * 4; const int d[4] = { +1, -X, -1, +X }; // Automaton初期化 for( int s = 0; s < 2; s ++ ){ a.succ[s].resize( n ); a.prev[s].resize( n ); for( int i = 0; i < n; i ++ ){ a.succ[s][i] = -1; a.prev[s][i].clear(); } } // 最初の向きを決め、まず壁に当たるまで歩く int dir; for( dir = 0; dir < 4; dir ++ ) if( b[start + d[dir]] == 0 ) break; if( dir == 4 ) -- dir; // テスト用 while( b[start + d[dir]] == 0 ) start += d[dir]; // BFS開始 queue< int > wl; vector< int > visited( n, 0 ); int state = start * 4 + dir; wl.push( state ); visited[state] = 1; while( !wl.empty() ){ int state1 = wl.front(); int pos = state1 / 4; int dir = state1 % 4; // printf( "(%d, %d), %d\n", pos % X, pos / X, dir ); wl.pop(); for( int s = 0; s < 2; s ++ ){ // 0: 左に曲がる 1: 右に曲がる int dir2 = (s == S_LEFT) ? ((dir + 1) % 4) : ((dir + 3) % 4); int pos2 = pos; // 曲がって壁に突き当たるまで歩く while( b[pos2 + d[dir2]] == 0 ) pos2 += d[dir2]; int state2 = pos2 * 4 + dir2; a.succ[s][state1] = state2; a.prev[s][state2].push_back( state1 ); if( visited[state2] == 0 ){ wl.push( state2 ); visited[state2] = 1; } } } int f_goal_reached = 0; for( int dir2 = 0; dir2 < 4; dir2 ++ ){ int state2 = goal * 4 + dir2; if( visited[state2] ){ f_goal_reached = 1; break; } } if( f_goal_reached ) return state; else return -1; } #define CONS(F,B) ((F)*n+(B)) #define CAR(N) ((N)/n) #define CDR(N) ((N)%n) // 0: not reached to Master at all // 1: not returned to Kitchen // 2: returned to Kitchen int solve( const vector< int > &b, // 1: wall 0: floor int X, int Y, int start, int goal, string &path ) { int n = b.size() * 4; Automaton a_forward, a_backward; int start_forward = create_automaton( b, X, Y, start, goal, a_forward ); if( start_forward < 0 ) return 0; int start_backward = create_automaton( b, X, Y, goal, start, a_backward ); queue< int > wl; vector< int > visited( n * n, 0 ); vector< int > prev_state( n * n, -1 ); vector< int > prev_s ( n * n, -1 ); for( int dir2 = 0; dir2 < 4; dir2 ++ ){ int state2 = CONS( start_forward, start * 4 + dir2 ); if( !visited[state2] ){ wl.push( state2 ); visited[state2] = 1; } } while( !wl.empty() ){ int state1 = wl.front(); int F = CAR( state1 ); int B = CDR( state1 ); wl.pop(); for( int s = 0; s < 2; s ++ ){ // 0: 左に曲がる 1: 右に曲がる int F2 = a_forward.succ[s][F]; for( vector< int >::iterator it = a_backward.prev[1-s][B].begin(), ite = a_backward.prev[1-s][B].end(); it != ite; ++ it ){ int B2 = *it; int state2 = CONS( F2, B2 ); if( !visited[state2] ){ wl.push( state2 ); visited[state2] = 1; prev_state[state2] = state1; prev_s [state2] = s; } if( F2 / 4 == goal && B2 == start_backward ){ if( DEBUG ){ path = ""; while( prev_state[state2] >= 0 ){ path = ("LR"[prev_s[state2]]) + path; // printf( "(%d, %d), (%d, %d)\n", CAR(state2)/4%X, CAR(state2)/4/X, CDR(state2)/4%X, CDR(state2)/4/X ); state2 = prev_state[state2]; } fprintf( stdout, "%s\n", path.c_str() ); } return 2; } } } } return 1; } const char *mes[3] = { "He cannot bring tea to his master.", "He cannot return to the kitchen.", "He can accomplish his mission." }; void normal_solver( void ) { char buf[1024]; int stat[3] = {0,0,0}; string dummy; for( int C = 1; ; C ++ ){ int X, Y; scanf( "%d%d", &X, &Y ); if( X == 0 && Y == 0 ) break; vector< int > b( X * Y, 0 ); int start = 0, goal = 0; for( int y = 0; y < Y; y ++ ){ scanf( "%s", buf ); for( int x = 0; x < X; x ++ ){ if( buf[x] == '#' ) b[x+y*X] = 1; else if( buf[x] == 'M' ) goal = x+y*X; else if( buf[x] == 'K' ) start = x+y*X; } } int r = solve( b, X, Y, start, goal, dummy ); printf( "%s\n", mes[r] ); } } int main( int argc, char *argv[] ) { normal_solver(); // 普通に解答出力 return 0; }