AOJ0121
問題:Seven Puzzle
スライドパズルの最短スワップ回数を求める。
幅優先した。
#include<iostream> #include<vector> #include<map> #include<algorithm> #include<queue> #include<cstdio> using namespace std; #define rep(i,n) for( int i=0; i<n; ++i ) #define INF 1<<21 int main() { map< vector<int> , int > memo; vector<int> in(8); rep(i,8)in[i]=i; do{ memo[ in ] = INF; }while(next_permutation(in.begin(),in.end())); sort(in.begin(),in.end()); queue<vector<int> > q; q.push(in); memo[in]=0; while( !q.empty() ) { in = q.front();q.pop(); int n = memo[in]; int i = 0; rep(o,8)if(in[o]==0)i=o; int l = i-1; int r = i+1; int u = i-4; int d = i+4; if( l >= 0 && l <= 7 && l !=3 ) { swap(in[i],in[l]); if( memo[in] == INF ) { memo[in] = n+1; q.push(in); } swap(in[i],in[l]); } if( r >= 0 && r <= 7 && r !=4 ) { swap(in[i],in[r]); if( memo[in] == INF ) { memo[in] = n+1; q.push(in); } swap(in[i],in[r]); } if( u >= 0 && u <= 7) { swap(in[i],in[u]); if( memo[in] == INF ) { memo[in] = n+1; q.push(in); } swap(in[i],in[u]); } if( d >= 0 && d <= 7 ) { swap(in[i],in[d]); if( memo[in] == INF ) { memo[in] = n+1; q.push(in); } swap(in[i],in[d]); } } while( 8 == scanf("%d %d %d %d %d %d %d %d", &in[0],&in[1],&in[2],&in[3],&in[4],&in[5],&in[6],&in[7]) ) { cout << memo[ in ] << endl; } }