Cubic Eight-Puzzle
2007.09.04 16:46 ACM/ICPC 2006
[問題] ACM/ICPC Asia Regional 2006 Yokohama: Problem C
[難易度] ★★★☆
[解説]
この問題の難易度は、本番のタイムリミットによって大きく左右します(★★☆くらいかも)。
(実際のタイムリミットはどのくらいだったのでしょうか?orz)
まず、考えられるのが単純な幅優先探索(横型探索)ですが、
審判データで試すと、手元のマシンで3分ほどかかってしまいます。(実装力の問題ですかね
)
この問題では、ゴールの状態数が大きいので、両側探索にする
メリットもあまりなさそうですし、実装も面倒臭そうだったのですが、
試してみると、案の定劇的な変化はなく30秒程度かかります。(これも実装力かなorz)
結局、問題の性質からして、反復深化(Iterative Deepening)(縦型探索)
がベストという結論に至りました。審判データを5秒弱で解けますし、
実装も簡単です。
選手の皆さんはどうやって解いたのでしょうか。。
何かポイントがありそうです(探索空間を縮小できるとか)。
この問題を縦型探索で解くには多少勇気がいる気がします。
マンハッタン距離を、現在の状態とゴールの状態における各セル上面の色が違うものの個数としました。
その他、マンハッタン距離を大きくするポイントがあれば高速化できるでしょう。
また、反復進化のLIMITの増加値を3とすることで、多少高速化できました。
[サンプルプログラム]
[難易度] ★★★☆
[解説]
この問題の難易度は、本番のタイムリミットによって大きく左右します(★★☆くらいかも)。
(実際のタイムリミットはどのくらいだったのでしょうか?orz)
まず、考えられるのが単純な幅優先探索(横型探索)ですが、
審判データで試すと、手元のマシンで3分ほどかかってしまいます。(実装力の問題ですかね

この問題では、ゴールの状態数が大きいので、両側探索にする
メリットもあまりなさそうですし、実装も面倒臭そうだったのですが、
試してみると、案の定劇的な変化はなく30秒程度かかります。(これも実装力かなorz)
結局、問題の性質からして、反復深化(Iterative Deepening)(縦型探索)
がベストという結論に至りました。審判データを5秒弱で解けますし、
実装も簡単です。
選手の皆さんはどうやって解いたのでしょうか。。
何かポイントがありそうです(探索空間を縮小できるとか)。
この問題を縦型探索で解くには多少勇気がいる気がします。
マンハッタン距離を、現在の状態とゴールの状態における各セル上面の色が違うものの個数としました。
その他、マンハッタン距離を大きくするポイントがあれば高速化できるでしょう。
また、反復進化のLIMITの増加値を3とすることで、多少高速化できました。
[サンプルプログラム]
001 #include<iostream> 002 #include<algorithm> 003 using namespace std; 004 005 struct Point{int x, y;}; 006 007 class Cube{ 008 public: 009 char C[3]; 010 Cube(){ C[0] = 'W'; C[1] = 'R'; C[2] = 'B';} 011 void setEmpty(){ C[0] = 'E';} 012 void rotate(int d){ 013 if ( d % 2 == 0 ) swap(C[0], C[2]); 014 else swap(C[0], C[1]); 015 } 016 }; 017 018 char target[3][3]; 019 020 class Puzzle{ 021 public: 022 Cube cubes[3][3]; 023 Point empty; 024 int manhattanDist; 025 026 Puzzle(){ 027 for ( int y = 0; y < 3; y++ ){ 028 for ( int x = 0; x < 3; x++ ) cubes[y][x] = Cube(); 029 } 030 } 031 032 void setEmpty( int y, int x ){ 033 empty.x = x; empty.y = y; 034 cubes[y][x].setEmpty(); 035 } 036 037 void setmanhattanDist(){ 038 manhattanDist = 0; 039 for ( int y = 0; y < 3; y++ ){ 040 for ( int x = 0; x < 3; x++ ){ 041 if ( cubes[y][x].C[0] != target[y][x] ) manhattanDist++; 042 } 043 } 044 } 045 046 void upDate( int y, int x, int d ){ 047 if ( target[y][x] != cubes[y][x].C[0] ) manhattanDist += d; 048 } 049 }; 050 051 int ix, iy, tx, ty, limit; 052 Puzzle u; 053 static const int dy[4] = {0, -1, 0, 1}; 054 static const int dx[4] = {1, 0, -1, 0}; 055 056 057 bool dfs( int depth, int pre, int seq ){ 058 if ( depth + u.manhattanDist-1 > limit ) return false; 059 if ( u.manhattanDist == 0 ) return true; 060 061 int x, y, nx, ny; 062 063 y = u.empty.y; 064 x = u.empty.x; 065 066 Puzzle tmp = u; 067 068 for ( int d = 0; d < 4; d++ ){ 069 if ( pre != -1 && d == (pre+2)%4 ) continue; 070 ny = y + dy[d]; 071 nx = x + dx[d]; 072 if ( ny < 0 || nx < 0 || 3 <= nx || 3 <= ny ) continue; 073 074 u = tmp; 075 076 u.upDate(ny, nx, -1); 077 u.upDate(y, x, -1); 078 079 u.cubes[ny][nx].rotate(d); 080 u.cubes[y][x] = u.cubes[ny][nx]; 081 u.setEmpty(ny, nx); 082 083 u.upDate(ny, nx, 1); 084 u.upDate(y, x, 1); 085 086 if ( dfs( depth+1, d, seq) ) return true; 087 } 088 089 return false; 090 } 091 092 void compute(){ 093 Puzzle initial = Puzzle(); 094 initial.setEmpty(iy, ix); 095 initial.setmanhattanDist(); 096 int start = initial.manhattanDist -1; 097 while( start % 3 != 0 ) start--; 098 for ( limit = start; limit <= 30; limit+=3 ){ 099 u = initial; 100 if ( dfs( 0, -1, 0 ) ) { 101 if ( limit == 0 ) {cout << 0 << endl; return;} 102 limit -= 2; 103 u = initial; 104 if ( dfs(0, -1, 0 ) ) { 105 cout << limit << endl; 106 } else { 107 limit++; 108 u = initial; 109 if ( dfs(0, -1, 0) ) cout << limit << endl; 110 else cout << limit + 1 << endl; 111 } 112 return; 113 } 114 } 115 cout << -1 << endl; 116 } 117 118 bool input(){ 119 cin >> ix >> iy; 120 if ( ix == 0 && iy == 0 ) return false; 121 ix--; iy--; 122 for ( int y = 0; y < 3; y++ ){ 123 for ( int x = 0; x < 3; x++ ){ 124 cin >> target[y][x]; 125 if ( target[y][x] == 'E' ){ tx = x; ty = y; } 126 } 127 } 128 return true; 129 } 130 131 main(){ 132 while(input()) compute(); 133 }
スポンサーサイト
| コメント(3) | トラックバック(0) | ↑ページトップ |