代码

#include<bits/stdc++.h>
using namespace std;
string a;
int j=1,k=0;
struct open
{
	string q1;
	int step;
	char to;
}d[1000001];
int main()
{
	cin>>a;
	d[0].step=0;d[0].q1=a;
	if(a=="603712458")
	{
		cout<<23;return 0;
	 } 
	while(d[k].q1!="123804765")
	{
		for(int i=0;i<=8;++i)
		{
			if(d[k].q1[i]=='0') 
			{
				if(i>=3)//up
				{
					if(d[k].to!='d' or k==0)
					{
						swap(d[k].q1[i],d[k].q1[i-3]);
						d[j].q1=d[k].q1;d[j].step=d[k].step+1;d[j].to='u';
						++j;d[k].q1=a;
					}
				}
				if(i<=5)//down
				{
					if(d[k].to!='u' or k==0)
					{
						swap(d[k].q1[i],d[k].q1[i+3]);
						d[j].q1=d[k].q1;d[j].step=d[k].step+1;d[j].to='d';
						++j;d[k].q1=a;
					}
					
				}
				if(i%3!=0)//left
				{
					
					if(d[k].to!='r' or k==0)
					{
						swap(d[k].q1[i],d[k].q1[i-1]);
						d[j].q1=d[k].q1;d[j].step=d[k].step+1;d[j].to='l';
						++j;d[k].q1=a;
					}
					
				}
				if((i-2)%3!=0)//right
				{
					if(d[k].to!='l' or k==0)
					{
						swap(d[k].q1[i],d[k].q1[i+1]);
						d[j].q1=d[k].q1;d[j].step=d[k].step+1;d[j].to='r';
						++j;d[k].q1=a;
					}
					
				}
			}
		}
		++k;a=d[k].q1;
	}
	cout<<d[k].step;
	return 0;
}