0121 - Seven Puzzle

#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <utility>
using namespace std;

const int d[4]={-1, 1, -4, 4};

map<string,int> count;

void bfs(void)	{
	queue<string> que;

	que.push("01234567");
	while ( !que.empty() )	{
		string wk1=que.front(); que.pop();
		int pos=wk1.find('0');
		for (int i=0; i<4; ++i)
			if ( 0<=pos+d[i] && pos+d[i]<8 && !(pos==3 && i==1) &&  !(pos==4 && i==0) )	{
				string wk2=wk1;
				swap(wk2[pos],wk2[ pos+d[i] ]);
				if ( !count[wk2] )	{
					que.push(wk2);
					count[wk2]=count[wk1]+1;
				}
			}
	}
}

void Slove(int n)	{
	string str="";

	str+=(n+'0');
	for (int i=0; i<7; ++i)	{
		cin >> n;
		str+=(n+'0');
	}
	cout << count[str]-1 << endl;
}

int main(void)	{
	int n;

	count["01234567"]=1;
	bfs();
	while (cin >> n)
		Slove(n);
	return 0;
}

幅優先探索で最初に全通り試す方法で解きました。