Karakuri Doll からくり人形

今年もACM/ICPCの模擬国内予選が開催されました。さすがOB/OG会の皆さん、すばらしい問題セットでした。取り急ぎ、自分ができそうな問題でかつ一番難しそうなFを解いてみました。このような、発想と実装力が必要でかつストリーが面白い問題を作成された方に感謝です。こういう問題をどんどん学生に挑戦させたいですね。

[問題]ACM/ICPC 模擬国内予選 2007: Problem F

OB/OG 会の解説を参考にして実装してみました（お粗末なコードです）

001 #include<iostream>
002 #define WMAX 64
003 #define HMAX 16
004 
005 using namespace std;
006 
007 class State{
008     public:
009     int toX, toY, toD; // to
010     int frX, frY, frD; // from
011     State(){}
012 };
013 
014 static const int dx[4] = {0, -1, 0, 1};
015 static const int dy[4] = {1, 0, -1, 0};
016 
017 int W, H;
018 char G[HMAX][WMAX];
019 bool visited[HMAX][WMAX][4][HMAX][WMAX][4];
020 State start, goal;
021 
022 int getSpaceDirection( int x, int y ){
023     for ( int r = 0; r < 4; r++ )
024         if ( G[x+dx[r]][y+dy[r]] != '#' ) return r;
025 }
026 
027 int getOposite( int r ){
028     return (r+2)%4;
029 }
030 
031 void turnRight( int &r ){
032     r--;
033     if ( r < 0 ) r = 3;
034 }
035 
036 void turnLeft( int &r ){
037     r = (r+1)%4;
038 }
039 
040 void move( int &x, int &y, int r ){
041     while ( G[x+dx[r]][y+dy[r]] != '#' ) { x += dx[r]; y += dy[r]; }
042 }
043 
044 bool findSource( int &x, int &y, int r, int p){
045     while (1){
046         if ( G[x][y] == '#' ) return false;
047         if ( G[x+dx[p]][y+dy[p]] == '#' ) return true;
048         x += dx[r]; y += dy[r];
049     }
050 }
051 
052 bool check( State s, State g ){
053     if ( s.toX == g.toX && s.toY == g.toY &&
054         s.frX == g.frX && s.frY == g.frY && s.frD == g.frD )
055         return true;
056     return false;
057 }
058 
059 bool recursive2( State u ){
060     if ( check( u, goal)  ) return true;
061     visited[u.toX][u.toY][u.toD][u.frX][u.frY][u.frD] = true;
062     
063     State v;
064     int r;
065     // next: right
066     v = u;
067     turnRight( v.toD );
068     move( v.toX, v.toY, v.toD );
069     r = getOposite(v.frD);
070     turnRight( v.frD );
071     while ( findSource( v.frX, v.frY, r, v.frD ) ){
072         if ( !visited[v.toX][v.toY][v.toD][v.frX][v.frY][v.frD] &&
073             recursive2( v ) ) return true;
074         v.frX += dx[r];	v.frY += dy[r];
075     }
076     
077     // next: left
078     v = u;
079     turnLeft( v.toD );
080     move( v.toX, v.toY, v.toD );
081     r = getOposite(v.frD);
082     turnLeft( v.frD );
083     while ( findSource( v.frX, v.frY, r, v.frD ) ){
084         if ( !visited[v.toX][v.toY][v.toD][v.frX][v.frY][v.frD] &&
085             recursive2( v ) ) return true;
086         v.frX += dx[r];	v.frY += dy[r];
087     }
088     
089     return false;
090 }
091 
092 void init(){
093     memset(visited, 0, sizeof(bool)*WMAX*WMAX*HMAX*HMAX*4*4);
094 }
095 
096 bool recursive1( State u ){
097     if ( u.toX == goal.toX && u.toY == goal.toY ) return true;
098     visited[u.toX][u.toY][u.toD][0][0][0] = true;
099     State v;
100     // to right
101     v = u;
102     turnRight(v.toD);
103     move(v.toX, v.toY, v.toD );
104     if ( !visited[v.toX][v.toY][v.toD][0][0][0] &&
105         recursive1(v) ) return true;
106     // to left
107     v = u;
108     turnLeft(v.toD);
109     move(v.toX, v.toY, v.toD );
110     if ( !visited[v.toX][v.toY][v.toD][0][0][0] &&
111         recursive1(v) ) return true;
112     
113     return false;
114 }
115 
116 int compute(){
117     start.toD = getSpaceDirection(start.toX, start.toY);
118     start.frD = getOposite(getSpaceDirection(start.toX, start.toY) );
119     move(start.toX, start.toY, start.toD);
120     
121     goal.toD = getOposite(getSpaceDirection(goal.toX, goal.toY) );
122     goal.frD = getSpaceDirection(goal.toX, goal.toY);
123     move(goal.frX, goal.frY, goal.frD);
124     
125     // to - from
126     init();
127     for ( int r = 0; r < 4; r++ ){
128         if ( recursive2( start ) ) return 0;
129         turnLeft(start.frD);
130     }
131     
132     // to
133     init();
134     if ( recursive1( start ) ) return 1;
135     
136     return 2;
137 }
138 
139 bool input(){
140     cin >> W >> H;
141     if ( W == 0 && H == 0 ) return false;
142     for ( int i = 0; i < H; i++ ){
143         for ( int j = 0; j < W; j++ ) {
144             cin >> G[i][j];
145             if ( G[i][j] == 'K' )
146                 { start.toX = start.frX = i; start.toY = start.frY = j;}
147             if ( G[i][j] == 'M' )
148                 { goal.toX = goal.frX = i; goal.toY = goal.frY = j;}
149         }
150     }
151     return true;
152 }
153 
154 main(){
155     while ( input() ) {
156         int judge = compute();
157         if ( judge == 0 )
158             cout << "He can accomplish his mission." << endl;
159         else if ( judge == 1 )
160             cout << "He cannot return to the kitchen." << endl;
161         else
162             cout << "He cannot bring tea to his master." << endl;
163     }
164 }

ACM/ICPC 模擬国内予選2007

ID	問題	難易度	考察
A	Space Coconut Grab	★	-
B	Osaki	★☆	-
C	Surrounding Area	★★	-
D	Square Route	★☆	-
E	Lifeguard in the Pool	★★★★☆	grave
F	Karakuri Doll	★★★☆	○