洛谷 P2578 [ZJOI2005]九数码游戏【bfs+康托展开】

只有9!=362880个状态，用康托展开hash一下直接bfs即可

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int N=1000005,fac[]={1,1,2,6,24,120,720,5040,40320,362880},d1[]={4,1,2,7,5,3,8,9,6},d2[]={1,2,3,6,4,5,7,8,9};

int a[15],b[15],v[15],dis[N],la[N],tot;

long long s,t=123456789,ans[N];

int has(long long x)

{

	for(int i=9;i>=1;i--)

		a[i]=x%10,x/=10;

	int r=0;

	for(int i=1,sm;i<=9;i++)

	{

		sm=0;

		for(int j=i+1;j<=9;j++)

			if(a[j]<a[i])

				sm++;

		r+=fac[9-i]*sm;

	}

	return r;

}

long long rel(int x)

{

	memset(v,0,sizeof(v));

	long long r=0;

	for(int i=9;i>=1;i--)

	{

		int t=x/fac[i-1];

		x%=fac[i-1];

		for(int j=1,w=0;j<=9;j++)

			if(!v[j])

			{

				w++;

				if(w==t+1)

				{

					r=r*10+j;

					v[j]=1;

					break;

				}

			}

	}

	return r;

}

int main()

{

	for(int i=1,x;i<=9;i++)

		scanf("%d",&x),s=s*10+x+1;

	s=has(s),t=has(t);//cerr<<s<<" "<<t<<"   "<<rel(s)<<" "<<rel(t)<<endl;

	queue<int>q;

	dis[s]=1;

	q.push(s);

	while(!q.empty())

	{

		int u=q.front();//cerr<<u<<endl<<rel(u)<<endl;

		q.pop();

		if(u==t)

			break;

		long long x=rel(u),v1=0,v2=0;

		for(int i=9;i>=1;i--)

			a[i]=x%10,x/=10;

		for(int i=0;i<9;i++)

			v1=v1*10+a[d1[i]],v2=v2*10+a[d2[i]];//cerr<<v1<<" "<<v2<<endl;

		v1=has(v1),v2=has(v2);//cerr<<v1<<" "<<v2<<endl;

		if(!dis[v1])

			la[v1]=u,dis[v1]=dis[u]+1,q.push(v1);

		if(!dis[v2])

			la[v2]=u,dis[v2]=dis[u]+1,q.push(v2);

	}

	if(!dis[t])

	{

		puts("UNSOLVABLE");

		return 0;

	}

	printf("%d\n",dis[t]-1);

	for(int i=t;i!=s;i=la[i])

		ans[++tot]=rel(i);

	ans[++tot]=rel(s);

	for(int i=tot;i>=1;i--)

	{

		for(int j=1;j<=9;j++)

			a[j]=ans[i]%10-1,ans[i]/=10;

		printf("%d %d %d\n%d %d %d\n%d %d %d\n\n",a[9],a[8],a[7],a[6],a[5],a[4],a[3],a[2],a[1]);

	}

	return 0;

}

巴特西

洛谷 P2578 [ZJOI2005]九数码游戏【bfs+康托展开】

最新文章

热门文章