Karakuri Doll からくり人形
2007.06.25 15:08 ACM/ICPC
今年もACM/ICPCの模擬国内予選が開催されました。さすがOB/OG会の皆さん、すばらしい問題セットでした。取り急ぎ、自分ができそうな問題でかつ一番難しそうなFを解いてみました。このような、発想と実装力が必要でかつストリーが面白い問題を作成された方に感謝です。こういう問題をどんどん学生に挑戦させたいですね。
[問題]ACM/ICPC 模擬国内予選 2007: Problem F
OB/OG 会の解説を参考にして実装してみました(お粗末なコードです)
[問題]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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |