Gap

[問題] ACM/ICPC Asia Regional 2003 Aizu: Problem F

[解説]

幅優先探索。
詳細は後日。

[サンプルプログラム]

001 #include<iostream>
002 #include<stdio.h>
003 #include<queue>
004 #include<map>
005 using namespace std;
006 
007 class Gap{
008     public:
009     short buffer[4][8];
010     short pos[50];
011     short space[4];
012     
013     Gap(){}
014     
015     bool solved(){
016         for ( int i = 0; i < 4; i++ ){
017             for ( int j = 1; j < 7; j++ ){
018                 if ( buffer[i][j] != (i+1)*10 + (j+1) ) return false;
019             }
020         }
021         return true;
022     }
023     
024     bool operator < ( const Gap &g ) const{
025         for ( int i = 0; i < 4; i++ ){
026             for ( int j = 0; j < 8; j++ ){
027                 if ( buffer[i][j] == g.buffer[i][j] ) continue;
028                 return buffer[i][j] < g.buffer[i][j];
029             }
030         }
031         return false;
032     }
033 };
034 
035 Gap initial;
036 
037 int bfs(){
038     queue<Gap> Q;
039     map<Gap, bool> visited;
040     map<Gap, int> cost;
041     
042     Q.push(initial);
043     cost[initial] = 0;
044     visited[initial] = true;
045     
046     Gap u, v;
047     
048     while( !Q.empty() ){
049         u = Q.front(); Q.pop();
050         if ( u.solved() ) return cost[u];
051         
052         int si, sj, target;
053         for ( int s = 0; s < 4; s++ ){
054             si = u.space[s]/8; sj = u.space[s]%8;
055             if ( u.buffer[si][sj-1] == 0 ||
056             u.buffer[si][sj-1]%10 == 7 ) continue;
057             
058             target = u.buffer[si][sj-1] + 1;
059             v = u;
060             v.buffer[si][sj] = target;
061             v.buffer[v.pos[target]/8][v.pos[target]%8] = 0;
062             v.space[s] = v.pos[target];
063             v.pos[target] = si*8 + sj;
064             
065             if ( !visited[v] ){
066                 visited[v] = true;
067                 cost[v] = cost[u] + 1;
068                 Q.push(v);
069             }
070         }
071     }
072     
073     return -1;
074 }
075 
076 void compute(){
077     for ( int i = 0; i < 4; i++ ){
078         int v = 10*(i+1) + 1;
079         initial.buffer[i][0] = v;
080         initial.space[i] = initial.pos[v];
081         initial.buffer[initial.pos[v]/8][initial.pos[v]%8] = 0;
082         initial.pos[v] = i*8;
083     }
084     cout << bfs() << endl;
085 }
086 
087 void input(){
088     int x;
089     for ( int i = 0; i < 4; i++ ){
090         for ( int j = 1; j < 8; j++ ){
091             cin >> x;
092             initial.buffer[i][j] = x;
093             initial.pos[x] = i*8 + j;
094         }
095     }
096 }
097 
098 main(){
099     int tcase; cin >> tcase;
100     for ( int i = 0; i < tcase; i++ ){
101         input();
102         compute();
103     }
104 }