题目地址：http://poj.org/problem?id=1077
先根据奇偶性判断能否达到
然后A*算法
注意：open表里根据h的值能效率更快，因为类似无障碍的图，离终点最近就应该最先pop
更新的时候不用检查closed表和open表，所以直接优先队列+判重就好了
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct Node{int status;int f,g,h;int parent;int move;Node(int s,int g,int h,int p,int m):status(s),f(g+h),g(g),h(h),parent(p),move(m){}bool operator < (const Node& n) const {return h>n.h; //比较h比比较f效率更高 }
};
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;
}
priority_queue<Node> open;
vector<Node> closed;
map<int,int> inClosed;
void inline AddClosed(Node v){closed.push_back(v);inClosed[v.status]=closed.size()-1;
}
void A_Star(int s,int t)
{open.push(Node(s,0,h(s),-1,0));while(!open.empty()){Node u=open.top(); open.pop();AddClosed(u);int s=u.status;if(s==t) return ;for(int i=0;i<4;i++){int ns=move(s,i);if(ns==-1||inClosed.count(ns)) continue;Node v=Node(ns,u.g+1,h(ns),s,i); //不用检查是否在open表里，因为f大的出不来 open.push(v);}}
}
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;
}
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;}A_Star(s,t);char d[5]="udlr";vector<char> ans;for(Node i=closed[inClosed[t]];i.parent!=-1;i=closed[inClosed[i.parent]])ans.push_back(d[i.move]);for(int i=ans.size()-1;i>=0;i--) cout<<ans[i];return 0;
}