fc2ブログ



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とすることで、多少高速化できました。
[サンプルプログラム]

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) | ↑ページトップ |

この記事へのコメント

本番のTimeLimitは非常に甘いです.審判データに対して3分がTimeLimitでCPUはPentium4 3.4GHz(らしい).
一応どんな解法でもちゃんと探索できているプログラムは大体通るようになってたみたいです.

審判データに対してはIterative Deepeningより普通の深さ制限付きDFSの方が高速で,
ローカルで2-3秒でした.
(深さの制限を最初は30にしておき,深さDの解が見つかると深さの制限D-1にする方法)
CIIやPOJのRanklistを見てみるとちゃんとDFSを書くほうが高速っぽいですね.

laycurse | URL | 2007.09.04 21:49

CIIやPOJのRanklistを見てみるとちゃんとDFSを書くほうが高速っぽいですね.
 ↓
CIIやPOJのRanklistを見てみるとちゃんとBFSを書くほうが高速っぽいですね.

ですね.BFSだとちゃんと状態数の上限が計算できて,たぶん大丈夫だ,と自信もって書けるのがいいですね.
盤面の圧縮とかがちょっと面倒ですが.

laycurse | URL | 2007.09.04 21:58

>laycurseさん

コメントありがとうございました!非常に参考になりました。
普通の深さ優先探索にしたら、2,3秒速くなりました!ビックリです。
私の実装の場合、POJは大丈夫でしたがCIIに通すにはもうすこし努力が必要ぽいですorz。
確かにRank上位者のメモリ使用量をみると、きちんとしたBFSがよさそうですね。

やはり本番のTLは甘かったのですね。
風船の数が多かったわりには、難しいなぁと思っていたところです。

utk | URL | 2007.09.05 00:33 | 編集

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ