题目在此

思路：很经典的搜索。时间比较紧，用map会T。hash函数用了 康托展开。

#include 
  
   
#include 
   
     #define INF 99999999 using namespace std; struct S{ int pos,mp[9],step; bool operator<(const S &p) const { return step>p.step; } }t; int fact[9]={1,1,2,6,24,120,720,5040,40320};//康托展开需要用到 inline int hashval(const int *s)//康托展开 { int sum=0; for(int i=0;i<9;i++) { int num=0; for(int j=0;j
    
     s[i]) num++; sum+=(num*fact[i]); } return sum; } int vis[362800],nxt[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int main() { int a,b,i,goal[9],key,oldpos,nx,ny; while(~scanf("%d%d",&a,&b) && a+b) { for(i=0;i<9;i++) { scanf("%d",&t.mp[i]); if(!t.mp[i]) t.pos=i; } for(i=0;i<9;i++) scanf("%d",&goal[i]); priority_queue
     que; for(i=0;i<362800;i++) vis[i]=INF; t.step=0; que.push(t); vis[hashval(t.mp)]=0; while(!que.empty()) { t=que.top(); for(i=0;i<9;i++) if(t.mp[i]!=goal[i]) break; if(i==9) { printf("%d\n",t.step); break; } que.pop(); for(i=0;i<4;i++) { oldpos=t.pos; nx=t.pos/3+nxt[i][0]; ny=t.pos%3+nxt[i][1]; if(nx==3) nx=0; if(nx==-1) nx=2; if(ny==3) { ny=0; nx++; if(nx==3) nx=0; } if(ny==-1) { ny=2; nx--; if(nx==-1) nx=2; } swap(t.mp[nx*3+ny],t.mp[oldpos]); if(i<2) t.step+=a; else t.step+=b; key=hashval(t.mp); if(t.step