A*算法

裸板子

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #define N 500005 8 using namespace std; 9 int jc[10],vis[N],fa[N],tp,stk[N],ans[N]; 10 int pos[9][2]={ { 0,0},{ 0,0},{ 0,1},{ 0,2},{ 1,0},{ 1,1},{ 1,2},{ 2,0},{ 2,1}}; 11 int dx[4]={ 0,0,-1,1}; 12 int dy[4]={-1,1,0,0}; 13 char tow[4]; 14 struct node 15 { 16 int mp[3][3]; 17 int f; 18 int g; 19 int h; 20 int xx,yy; 21 bool friend operator < (node x,node y) 22 { 23 return x.f!=y.f?x.f>y.f:x.g
            
             st[i*3+j]); 41 } 42 } 43 } 44 } 45 } 46 return 1-(cnt&1); 47 } 48 int sol(node x) 49 { 50 int st[12],ret=0; 51 for(int i=0;i<3;i++) 52 { 53 for(int j=0;j<3;j++) 54 { 55 st[i*3+j]=x.mp[i][j]; 56 int cnt=0; 57 for(int k=0;k
             
              st[i*3+j]); 60 } 61 ret+=jc[i*3+j]*cnt; 62 } 63 } 64 return ret; 65 } 66 int work(node x) 67 { 68 int ret=0; 69 for(int i=0;i<3;i++) 70 { 71 for(int j=0;j<3;j++) 72 { 73 if(x.mp[i][j]!=9) 74 { 75 ret+=abs(pos[x.mp[i][j]][0]-i)+abs(pos[x.mp[i][j]][1]-j); 76 } 77 } 78 } 79 return ret; 80 } 81 void bfs() 82 { 83 memset(vis,0,sizeof(vis)); 84 priority_queue
              
               q; 85 sta.g=0,sta.h=work(sta); 86 sta.f=sta.g+sta.h; 87 q.push(sta); 88 while(!q.empty()) 89 { 90 node tmp=q.top();q.pop(); 91 int now=sol(tmp); 92 for(int i=0;i<4;i++) 93 { 94 node nxt=tmp; 95 nxt.xx+=dx[i]; 96 nxt.yy+=dy[i]; 97 if(nxt.xx<0||nxt.xx>2||nxt.yy<0||nxt.yy>2) 98 { 99 continue;100 }101 nxt.mp[tmp.xx][tmp.yy]=tmp.mp[nxt.xx][nxt.yy];102 nxt.mp[nxt.xx][nxt.yy]=9;103 nxt.g++;104 nxt.h=work(nxt);105 nxt.f=nxt.g+nxt.h;106 int jr=sol(nxt);107 if(vis[jr])108 {109 continue;110 }111 vis[jr]=1;112 fa[jr]=now;113 ans[jr]=i;114 q.push(nxt);115 if(!jr)116 {117 return;118 }119 }120 }121 }122 int main()123 {124 jc[0]=1;125 for(int i=1;i<=9;i++)126 {127 jc[i]=jc[i-1]*i;128 }129 tow[0]='l',tow[1]='r',tow[2]='u',tow[3]='d';130 int tx=0,ty=0;131 for(int i=0;i<9;i++)132 {133 char ch[2];134 scanf("%s",ch);135 if(ch[0]=='x')136 {137 ch[0]='9';138 sta.xx=tx,sta.yy=ty;139 }140 sta.mp[tx][ty]=ch[0]-'0';141 ty++;142 if(ty>=3)143 {144 ty-=3;145 tx++;146 }147 }148 if(!check(sta))149 {150 puts("unsolvable");151 return 0;152 }153 int aim=sol(sta);154 bfs();155 int col=0;156 while(col!=aim)157 {158 stk[++tp]=col;159 col=fa[col];160 }161 while(tp)162 {163 printf("%c",tow[ans[stk[tp]]]);164 tp--;165 }166 puts("");167 return 0;168 }