题目地址：http://poj.org/problem?id=1077
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
struct Node{int status;int parent;int move;Node(int s=0,int p=0,int m=-1):status(s),parent(p),move(m){}
};
int toInt(int *A)
{int x=0;for(int i=0;i<9;i++)x=x*10+A[i];return x;
}
int toIntArray(int A[],int s)
{int p;for(int i=8;i>=0;i--){A[i]=s%10;if(!A[i]) p=i;s/=10;}return p;
}
int h(int status)
{int cnt=0;int a[9];toIntArray(a,status); for(int i=0;i<3;i++)for(int j=0;j<3;j++){int n=a[i*3+j]-1;int x=n/3,y=n%3;if(n==-1) x=y=2;cnt+=abs(x-i)+abs(y-j);}return cnt;
}
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
bool inside(int x,int y){return x>=0&&x<3&&y>=0&&y<3;
}
int move(int s,int i)
{int b[9];int p=toIntArray(b,s);int x=p/3,y=p%3;int nx=x+dx[i],ny=y+dy[i];;if(!inside(nx,ny)) return -1;int np=nx*3+ny;swap(b[np],b[p]);int ns=toInt(b);return ns;
}
int fac[]={1,1,2,6,24,120,720,5040,40320};
int rank(int s)
{ int a[9]; toIntArray(a,s);int res=0,k; for(int i=0;i<9;i++) { k=0; for(int j=i+1;j<9;j++) if(a[i]>a[j]) k++; res+=k*fac[9-1-i]; } return res;
}
Node DQ[2][400000];
bool vis[2][400000];
int front[2]={1,1},rear[2]={0,0};
int matchQ,matchState;
void DBFS(int s,int t)
{DQ[0][0]=Node(s,-1,0);DQ[1][0]=Node(t,-1,0);vis[0][rank(s)]=true;vis[1][rank(t)]=true;while(front[0]!=rear[0]||front[1]!=rear[1]){int QNo;if(front[0]==rear[0]) QNo=1;else if(front[1]==rear[1]) QNo=0;else {if(front[0]-rear[0]<front[1]-rear[1]) QNo=0; //哪个少就更新哪个 else QNo=1;}int VQNo=1-QNo;Node u=DQ[QNo][rear[QNo]]; int state=u.status;if(vis[VQNo][rank(state)]) {matchQ=QNo;matchState=state;return;}for(int i=0;i<4;i++){int ns=move(state,i),r=rank(ns);if(ns==-1||vis[QNo][r]) continue;vis[QNo][r]=true;DQ[QNo][front[QNo]++]=Node(ns,rear[QNo],i); //不用检查是否在open表里，因为f大的出不来 }rear[QNo]++; }
}
bool bSolved(int s){ //根据奇偶性，预判是否可以解决 int cnt=0,a[9];toIntArray(a,s);for(int i=0;i<9;i++){if(!a[i]) continue;for(int j=i+1;j<9;j++){if(!a[j]) continue;if(a[i]>a[j]) cnt++;}}return cnt&1;
}
void Print() //输出答案
{char d[5]="udlr";string ans; int p;if(matchQ==0) p=rear[0];else for(int i=0;i<front[0];i++)if(DQ[0][i].status==matchState){p=i; break;}while(p){ans+=d[DQ[0][p].move];p=DQ[0][p].parent;}reverse(ans.begin(),ans.end());if(matchQ==0){for(int i=0;i<front[1];i++)if(DQ[1][i].status==matchState){p=i; break;}}else p=rear[1];while(p){ans+=d[DQ[1][p].move^1];p=DQ[1][p].parent;}cout<<ans<<endl;
}
int main()
{int a[10];char ch;for(int i=0;i<9;i++) {cin>>ch;if(isdigit(ch)) a[i]=ch-'0';else a[i]=0;}int s=toInt(a),t=123456780;if(bSolved(s)){cout<<"unsolvable"; return 0;}DBFS(s,t);Print();return 0;
}