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;
	}
	
}