Cubic Eight-Puzzle

[問題] ACM/ICPC Asia Regional 2006 Yokohama: Problem C

[難易度]　★★★☆

[解説]

この問題の難易度は、本番のタイムリミットによって大きく左右します（★★☆くらいかも）。
(実際のタイムリミットはどのくらいだったのでしょうか？orz)

まず、考えられるのが単純な幅優先探索（横型探索）ですが、
審判データで試すと、手元のマシンで３分ほどかかってしまいます。(実装力の問題ですかね)
この問題では、ゴールの状態数が大きいので、両側探索にする
メリットもあまりなさそうですし、実装も面倒臭そうだったのですが、
試してみると、案の定劇的な変化はなく３０秒程度かかります。（これも実装力かなorz）

結局、問題の性質からして、反復深化（Iterative Deepening）（縦型探索）
がベストという結論に至りました。審判データを５秒弱で解けますし、
実装も簡単です。
選手の皆さんはどうやって解いたのでしょうか。。
何かポイントがありそうです（探索空間を縮小できるとか）。
この問題を縦型探索で解くには多少勇気がいる気がします。

マンハッタン距離を、現在の状態とゴールの状態における各セル上面の色が違うものの個数としました。
その他、マンハッタン距離を大きくするポイントがあれば高速化できるでしょう。
また、反復進化のＬＩＭＩＴの増加値を３とすることで、多少高速化できました。
[サンプルプログラム]

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 }