样例过了，但除了#4 and #26 AC，#31 WA 以外，全抄空间了，先加一个预期花费数组初始为0，再将每个格子距离自己应该待的地方的距离的和按照预期花费+已花费排升序，认为思路没问题.

#include <iostream>
using namespace std;
/*
273
645
801

273645801
*/
int a[5000001][4][4],t,x[5000001],y[5000001],h=1,as[4][4],top=2,flag=1,cost[5000001];
int main()
{
	string s;
	cin>>s;
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			a[1][i][j]=s[i*3-3+j-1]-48;
			if(!a[1][i][j])
			{
				x[h]=i;
				y[h]=j;
			}
		}
	}
	as[1][1]=1;
	as[1][2]=2;
	as[1][3]=3;
	
	as[2][1]=8;
	as[2][2]=0;
	as[2][3]=4;
	as[3][1]=7;
	as[3][2]=6;
	as[3][3]=5;

	while(flag&&h<top)
	{
		if(x[h]>1)
		{
			x[top]=x[h]-1;
			y[top]=y[h];
			cost[top]=cost[h]+1;
			a[top][1][1]=a[h][1][1];
			a[top][1][2]=a[h][1][2];
			a[top][1][3]=a[h][1][3];
			a[top][2][1]=a[h][2][1];
			a[top][2][2]=a[h][2][2];
			a[top][2][3]=a[h][2][3];
			a[top][3][1]=a[h][3][1];
			a[top][3][2]=a[h][3][2];
			a[top][3][3]=a[h][3][3];
			swap(a[top][x[top]][y[top]],a[top][x[h]][y[h]]);
			t=1;
			for(int i=1;i<=3&&t;i++)
			{
				for(int j=1;j<=3&&t;j++)
				{
					if(a[top][i][j]!=as[i][j])t=0;
				}
			}
			if(t)
			{
				cout<<cost[top];
				flag=0;
				return 0;
			}
			top++;
		}
		if(y[h]>1)
		{
			x[top]=x[h];
			y[top]=y[h]-1;
			cost[top]=cost[h]+1;
			a[top][1][1]=a[h][1][1];
			a[top][1][2]=a[h][1][2];
			a[top][1][3]=a[h][1][3];
			a[top][2][1]=a[h][2][1];
			a[top][2][2]=a[h][2][2];
			a[top][2][3]=a[h][2][3];
			a[top][3][1]=a[h][3][1];
			a[top][3][2]=a[h][3][2];
			a[top][3][3]=a[h][3][3];
			swap(a[top][x[top]][y[top]],a[top][x[h]][y[h]]);
			t=1;
			for(int i=1;i<=3&&t;i++)
			{
				for(int j=1;j<=3&&t;j++)
				{
					if(a[top][i][j]!=as[i][j])t=0;
				}
			}
			if(t)
			{
				cout<<cost[top];
				flag=0;
				return 0;
			}
			top++;
		}
		if(x[h]<3)
		{
			x[top]=x[h]+1;
			y[top]=y[h];
			cost[top]=cost[h]+1;
			a[top][1][1]=a[h][1][1];
			a[top][1][2]=a[h][1][2];
			a[top][1][3]=a[h][1][3];
			a[top][2][1]=a[h][2][1];
			a[top][2][2]=a[h][2][2];
			a[top][2][3]=a[h][2][3];
			a[top][3][1]=a[h][3][1];
			a[top][3][2]=a[h][3][2];
			a[top][3][3]=a[h][3][3];
			swap(a[top][x[top]][y[top]],a[top][x[h]][y[h]]);
			t=1;
			for(int i=1;i<=3&&t;i++)
			{
				for(int j=1;j<=3&&t;j++)
				{
					if(a[top][i][j]!=as[i][j])t=0;
				}
			}
			if(t)
			{
				cout<<cost[top];
				flag=0;
				return 0;
			}
			top++;
		}
		if(y[h]<3)
		{
			x[top]=x[h];
			y[top]=y[h]+1;
			cost[top]=cost[h]+1;
			a[top][1][1]=a[h][1][1];
			a[top][1][2]=a[h][1][2];
			a[top][1][3]=a[h][1][3];
			a[top][2][1]=a[h][2][1];
			a[top][2][2]=a[h][2][2];
			a[top][2][3]=a[h][2][3];
			a[top][3][1]=a[h][3][1];
			a[top][3][2]=a[h][3][2];
			a[top][3][3]=a[h][3][3];
			swap(a[top][x[top]][y[top]],a[top][x[h]][y[h]]);
			t=1;
			for(int i=1;i<=3&&t;i++)
			{
				for(int j=1;j<=3&&t;j++)
				{
					if(a[top][i][j]!=as[i][j])t=0;
				}
			}
			if(t)
			{
				cout<<cost[top];
				flag=0;
				return 0;
			}
			top++;
		}
		h++;
	}
	return 0;
}