Gap
2007.08.23 12:51 ACM/ICPC 2003
[問題] 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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |