题目（A*写法

code:

#include<bits/stdc++.h>
using namespace std;
int n,ans=0,a[10][10],pd,sx,sy;
struct nn{
	int x,y;
};
int gx[10]={0,1,1,1,2,3,3,3,2};
int gy[10]={0,1,2,3,3,3,2,1,1};
int dx[10]={0,1,-1,0,0};
int dy[10]={0,0,0,-1,1};
int g(){//估价函数 
	nn xz[10];
	int res=0;
	for(int i=1;i<=3;i++){
		for(int k=1;k<=3;k++){
			xz[a[i][k]].x=i;
			xz[a[i][k]].y=k;
		}
	}
	for(int i=1;i<=8;i++){
		res+=abs(xz[i].x-gx[i])+abs(xz[i].y-gy[i]);//用欧几里得距离存为估计距离 
	}
	return res;
}
void dfs(int xz,int goal,int x,int y){
	int v=g();
	if(pd||xz>goal||xz+v>goal||!v){//若当前所用+估价>ans,则ans++或返回，因为不能在这个步数到达 
		if(!v)pd=1;
		return ;
	}
	for(int i=1;i<=4;i++){
		int tx=x+dx[i],ty=y+dy[i];
		if(tx<1||ty<1||tx>3||ty>3)continue;
		swap(a[x][y],a[tx][ty]);
		dfs(xz+1,goal,tx,ty);
		swap(a[x][y],a[tx][ty]);//复原 
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=3;i++){
		for(int k=1;k<=3;k++){
			a[4-i][4-k]=n%10;
			n/=10;
			if(!a[4-i][4-k]){
				sx=i;
				sy=k;
			}
		}
	}
	while(!pd){
		ans++;
		dfs(0,ans,sx,sy);
	}
	cout<<ans;
	return 0;
}

求条,求求了！！