http://poj.org/problem?id=1077
http://acm.hdu.edu.cn/showproblem.php?pid=1043
X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中，a[i]为整数，并且X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!。这就是康托展开。康拓展开可以用来表示排列状态,对于本题的9个数字的所有排列只需要9位,所有状态总共362880个.对每个状态,我们都能得到一个不重复的状态编号,用这个状态编号可以查重
Astar算法,就是一个给所有状态一个评估函数,优先选取较优状态向下搜的最好优先直接搜索算法,对于本题,我们设F(n)=g(n)+h(n)为估价函数,设g(n)为到达该状态已经走过的步数,h(n)为到最终答案的曼哈顿距离
因为该拼图不能改变除了x以外的数字的逆序数奇偶性,所以若x以外的数字逆序数为奇数,则无法得到答案,直接输出
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cctype>
using namespace std;
const int base[9]={1,1,2,6,24,120,720,5040,40320};
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
const int maxh=362880;
const int des=0;
struct pnt{
int maz[3][3];
int h,g;
int x,y;
int hashCode;
bool operator < (pnt p)const {
return h+g!=p.h+p.g?h+g>p.h+p.g:g>p.g;
}
int gethashcode(){
int ans=0;
for(int i=0;i<9;i++){
int cnt=0;
for(int j=0;j<i;j++){
if(maz[j/3][j%3]>maz[i/3][i%3]){
cnt++;
}
}
ans+=base[i]*cnt;
}
return hashCode=ans;
}
int geth(){
int ans=0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
int t=maz[i][j]-1;
if(t<9) ans+=abs(i-t/3)+abs(j-t%3);
}
}
return ans;
}
bool judge(){
int cnt=0;
for(int i=0;i<9;i++){
for(int j=0;j<i;j++){
if(maz[i/3][i%3]<9&&maz[j/3][j%3]<9&&maz[i/3][i%3]<maz[j/3][j%3])cnt++;
}
}
return (cnt&1)==0;
}
};
bool in(int tx,int ty){
return tx>=0&&tx<3&&ty>=0&&ty<3;
} int vis[maxh+1];
int pre[maxh+1]; void astar(pnt s){
priority_queue <pnt>que;
que.push(s);
while(!que.empty()){
pnt f=que.top();que.pop();
for(int i=0;i<4;i++){
pnt t=f;
t.x+=dx[i];
t.y+=dy[i];
if(in(t.x,t.y)){
swap(t.maz[t.x][t.y],t.maz[f.x][f.y]);
t.hashCode=t.gethashcode();
if(vis[t.hashCode]==-1){
vis[t.hashCode]=i;
t.g++;
pre[t.hashCode]=f.hashCode;
t.h=t.geth();
que.push(t);
}
if(t.hashCode==des)return ;
}
}
}
}
char ans[maxh+1];
void print(){
int nxt=des;
int len=0;
while(pre[nxt]!=-1){
switch(vis[nxt]){
case 0:
ans[len++]='d';
break;
case 1:
ans[len++]='u';
break;
case 2:
ans[len++]='r';
break;
case 3:
ans[len++]='l';
break;
}
nxt=pre[nxt];
}
for(int i=len-1;i>=0;i--){
putchar(ans[i]);
}
puts("");
}
char buff[300];
pnt s;
bool input(){
if(gets(buff)==NULL)return false;
int j=0;
for(int i=0;i<9;i++){
while(!isalnum(buff[j])){j++;}
if(buff[j]>='0'&&buff[j]<='9'){
s.maz[i/3][i%3]=buff[j]-'0';
}
else{
s.maz[i/3][i%3]=9;
s.x=i/3;
s.y=i%3;
}
j++;
}
return true;
}
int main(){
while(input()){
memset(vis,-1,sizeof(vis));
memset(pre,-1,sizeof(pre));
if(!s.judge()){
puts("unsolvable");
continue;
}
s.hashCode=s.gethashcode();
if(s.hashCode==des){
puts("");
continue;
}
vis[s.hashCode]=-2;
s.g=0;s.h=s.geth();
astar(s);
print();
}
return 0;
}