学步园

#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int PermSize=9;
int factory[20]={0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800};
bool used[362880];
char goal[9];
struct node
{
	int x,step;
	char s[9];
};
int cantor(const char* buf)
{
	int i,j,counted;
	int result=0;
	for(i=0;i<PermSize;++i)
	{
		counted=0;
		for(j=i+1;j<PermSize;++j)
			if(buf[i]>buf[j])
				++counted;
		result=result+counted*factory[PermSize-i-1];
	}
	return result;
}
void bfs(node st)
{
	int i,j,k;
	node now,next;
	queue<node>qq;
	qq.push(st);
	while(qq.size())
	{
		now=qq.front();
		qq.pop();
		i=now.x/3;
		j=now.x%3;
		if(i>0)
		{
			next.x=(i-1)*3+j;
			next.step=now.step+1;
			strcpy(next.s,now.s);
			swap(next.s[now.x],next.s[next.x]);
			k=cantor(next.s);
			if(!used[k])
			{
				qq.push(next);
				if(strcmp(next.s,goal)==0)
				{
					cout<<next.step;
					return;
				}
				used[k]=1;
			}
		}
		if(i<2)
		{
			next.x=(i+1)*3+j;
			next.step=now.step+1;
			strcpy(next.s,now.s);
			swap(next.s[now.x],next.s[next.x]);
			k=cantor(next.s);
			if(!used[k])
			{
				qq.push(next);
				if(strcmp(next.s,goal)==0)
				{
					cout<<next.step;
					return;
				}
				used[k]=1;
			}
		}
		if(j>0)
		{
			next.x=i*3+j-1;
			next.step=now.step+1;
			strcpy(next.s,now.s);
			swap(next.s[now.x],next.s[next.x]);
			k=cantor(next.s);
			if(!used[k])
			{
				qq.push(next);
				if(strcmp(next.s,goal)==0)
				{
					cout<<next.step;
					return;
				}
				used[k]=1;
			}
		}
		if(j<2)
		{
			next.x=i*3+j+1;
			next.step=now.step+1;
			strcpy(next.s,now.s);
			swap(next.s[now.x],next.s[next.x]);
			k=cantor(next.s);
			if(!used[k])
			{
				qq.push(next);
				if(strcmp(next.s,goal)==0)
				{
					cout<<next.step;
					return;
				}
				used[k]=1;
			}
		}
	}
	cout<<-1;
}
int main()
{
	node st;
	scanf("%s%s",st.s,goal);
	if(strcmp(st.s,goal)==0)
	{
		cout<<0;
		return 0;
	}
	st.step=0;
	st.x=strstr(st.s,".")-st.s;
	used[cantor(st.s)]=1;
	bfs(st);
	return 0;
}

http://lx.lanqiao.org/problem.page?gpid=T42
问题描述