RT

代码：

#include<bits/stdc++.h>
using namespace std;

struct bsm
{
	int a[4][4];
}start,endg,q[1000001];

int power[20]={1,1,2,6,24,120,720,5040,40320,362880,3628800};
int vis[1000001]={0};
int step[1000001];
int endd;
int sta[10]={0,2,3,4,9,1,5,8,7,6};
int x[1000001];
int y[1000001];

int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};

int Cuntor(bsm x)
{
	int cnt=0,t[10],s;
	for(int i=1;i<=3;i++)
	for(int j=1;j<=3;j++)
		t[i*3-3+j]=x.a[i][j];
	for(int i=1;i<=9;i++)
	{
		s=0;
		for(int j=i+1;j<=9;j++)
			if(t[j]<t[i])
				s++;
		cnt+=power[9-i]*s;
	}
	return cnt;
}

bsm Change(int dir,int num,int kx,int ky)
{
	bsm t;
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			t.a[i][j]=q[num].a[i][j];
		}
	}
	if(dir==1)
	{
		swap(t.a[kx][ky],t.a[kx][ky+1]);
	}
	if(dir==2)
	{
		swap(t.a[kx][ky],t.a[kx][ky-1]);
	}
	if(dir==3)
	{
		swap(t.a[kx][ky],t.a[kx+1][ky]);
	}
	if(dir==4)
	{
		swap(t.a[kx][ky],t.a[kx-1][ky]);
	}
	return t;
}

void bfs()
{
	int head=1;
	int tail=1;
	bsm t;
	x[1]=y[1]=2;
	int tt;
	q[1]=start;
	step[1]=0;
	while(head<=tail)
	{
		for(int i=1;i<=4;i++)
		{
			tail++; 
			t=Change(i,head,x[head],y[head]);
			x[tail]=x[head]+dx[i];
			y[tail]=y[head]+dy[i];
			if(x[tail]<=0||y[tail]<=0||x[tail]>=4||y[tail]>=4)
			{	
				tail--; 
				continue;
			}
			//t=Change(i,head,x[tail],y[tail]);
			tt=Cuntor(t);
			if(vis[tt]==0)
			{
				q[tail]=t;
				step[tail]=step[head]+1;
				vis[tt]=1;
				//cout<<tt<<endl;
				//cout<<t.a[1][1]<<" "<<t.a[1][2]<<" "<<t.a[1][3]<<endl<<t.a[2][1]<<" "<<t.a[2][2]<<" "<<t.a[2][3]<<endl<<t.a[3][1]<<" "<<t.a[3][2]<<" "<<t.a[3][3]<<endl<<endl;
				if(tt==endd)
				{
					cout<<step[tail];
					return;
				}
			}
		}
		head++;
	}
}

int main()
{
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			start.a[i][j]=sta[i*3-3+j];
		}
	}
	int startt=Cuntor(start);
	//cout<<startt<<endl<<endl;
	vis[startt]=1;
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			char c;
			cin>>c; 
			endg.a[i][j]=char(c-'0'+1);
		}
	}
	endd=Cuntor(endg);
	//cout<<endd;
	//cout<<endl<<endl;
	if(endd==startt)
	{
		cout<<0;
		return 0;
	}
	bfs();
	//cout<<"NO.."<<endl; 
}
//283                283
//104				 104
//765				 765

注释的是调试部分