{{{ #!cplusplus /* zju 1217 HDu 1043 ymc 2008/5/28 解题思路: 把x看作0,则每种状态对应012345678的一个排列。终止状态为123456780。 012345678总共有有9!种排列,按照字典顺序给所有的排列排序,012345678在最前面,876543210在最后面。 ptonum() 求出一个排列的序号 numtop() 给出给定序号的排列 从开始状态到终止状态BFS搜索 TLE 反过来思BFS终止状态到所有状态的最短路径,对每次查询只要生成输出就可以 */ #include #include using namespace std; const int Max=362880; //9! const int N=9; int f[N]; int map[N]={1,2,3,4,5,6,7,8,0}; int Trans[Max][4]; //记录各种状态间的转移,每种状态最多转移到四种状态。上下左右 char Transop[Max][4];//各种状态转移的操作 int start,end; struct Operator { int next; char op; }; Operator OP[Max]; //其实状态到终止状态的最短路径以及操作(逆序) int ptonum(int a[]) //012345678的所有排列按照字典顺序排列,任意给出一个排列,计算在排列中的序号。 { bool used[N]; memset(used,0,sizeof(used)); int ans=0; int num; for(int i=0;i=3) //x上移 { tmp=b[k];b[k]=b[k-3];b[k-3]=tmp; v=ptonum(b); Trans[u][num]=v; Transop[u][num]='d'; num++; tmp=b[k];b[k]=b[k-3];b[k-3]=tmp; } if(k<6) //x下移 { tmp=b[k];b[k]=b[k+3];b[k+3]=tmp; v=ptonum(b); Trans[u][num]=v; Transop[u][num]='u'; num++; tmp=b[k];b[k]=b[k+3];b[k+3]=tmp; } if(k%3!=0) //x左移 { tmp=b[k];b[k]=b[k-1];b[k-1]=tmp; v=ptonum(b); Trans[u][num]=v; Transop[u][num]='r'; num++; tmp=b[k];b[k]=b[k-1];b[k-1]=tmp; } if(k%3!=2) //x右移 { tmp=b[k];b[k]=b[k+1];b[k+1]=tmp; v=ptonum(b); Trans[u][num]=v; Transop[u][num]='l'; num++; tmp=b[k];b[k]=b[k+1];b[k+1]=tmp; } } } int Reverse(int a[N]) { int sum=0; int b[N]; memset(b,0,sizeof(b)); for(int i=0;ia[i]) b[a[i]]++; sum+=b[a[i]]; } return sum-b[0]; } void PreBFS() { bool used[Max]; memset(used,0,sizeof(used)); // start=ptonum(map); queue q; q.push(end); used[end]=true; int u,v; while(!q.empty()) { u=q.front(); for(int i=0;Trans[u][i]!=0&&i<4;i++) { v=Trans[u][i]; if(!used[v]) { used[v]=true; OP[v].next=u; OP[v].op=Transop[u][i]; q.push(v); } } q.pop(); } } void output() { int st=start; while(st!=end) { cout<>ch) { if(ch!='x') map[0]=ch-'0'; else map[0]=0; for(int i=1;i>ch; if(ch!='x') map[i]=ch-'0'; else map[i]=0; } int tmp=Reverse(map); if(tmp%2!=0) { cout<<"unsolvable\n"; continue; } start=ptonum(map); output(); } } }}}