学步园

状态有9！种，用的全排列的hash。

首先写了个A*算法，0ms过了，但内存消耗挺大。其他方法的代码会陆续添加。

好久没写过这种2500B+的代码。

A*

#include <queue><br /> #include <algorithm><br /> #include <iostream><br /> #define _clr(a,b) memset(a,b,sizeof(a))<br /> using namespace std;<br /> const int maxn=362880;//9!<br /> const int end_state=0;//{0 1 2 3 4 5 6 7 8}是满足要求的排列，此时state=0<br /> int fac[9],state[9];//fac[i]=i!,fac[0]=0<br /> int move[4]={-1,1,-3,3};//4个方向的移动<br /> int h(int a[])//估价函数，好的估价函数是A*算法的命根<br /> {<br /> int ret=0;<br /> for(int i=0;i<9;i++) ret+=abs(a[i]-i);<br /> return ret;<br /> }<br /> int get_key(int a[])//全排列的hash，计算状态<br /> {<br /> int ret=0,count;<br /> for(int i=1;i<9;i++)<br /> {<br /> count=0;<br /> for(int j=0;j<i;j++) count+=a[j]>a[i]?1:0;<br /> ret+=count*fac[i];<br /> }<br /> return ret;<br /> }<br /> struct node//插到优先队列中<br /> {<br /> int tt[9];<br /> int state;<br /> int pos;<br /> int step;<br /> }start,next;<br /> struct node2//存储已经到达过的状态的信息，用于反演路径<br /> {<br /> int last_state;<br /> int pos;<br /> int step;<br /> }info[maxn];<br /> bool operator>(const node a,const node b)<br /> {<br /> return a.step>b.step;<br /> }<br /> priority_queue<node,vector<node>,greater<vector<node>::value_type>> my_queue;<br /> void Init()<br /> {<br /> fac[0]=0;<br /> fac[1]=1;<br /> for(int i=2;i<9;i++) fac[i]=fac[i-1]*i;<br /> }<br /> inline void intcpy(int a[],int b[])<br /> {<br /> for(int i=0;i<9;i++) a[i]=b[i];<br /> }<br /> bool Find_path()<br /> {<br /> while(!my_queue.empty())<br /> {<br /> start=my_queue.top();<br /> my_queue.pop();<br /> intcpy(next.tt,start.tt);<br /> for(int i=0;i<4;i++)<br /> {<br /> next.pos=start.pos+move[i];<br /> if(abs(move[i])==1&&(next.pos/3!=start.pos/3)) continue;//曾经因为这里，送了n次wa和n个小时的排错时间<br /> if(next.pos>=0&&next.pos<=8)<br /> {<br /> swap(next.tt[next.pos],next.tt[start.pos]);<br /> next.step=h(next.tt);<br /> next.state=get_key(next.tt);<br /> if(next.state==end_state)<br /> {<br /> info[next.state].last_state=start.state;<br /> info[next.state].pos=next.pos;<br /> return true;<br /> }<br /> if(info[next.state].step==-1)<br /> {<br /> info[next.state].step=next.step;<br /> info[next.state].last_state=start.state;<br /> info[next.state].pos=next.pos;<br /> my_queue.push(next);<br /> }<br /> swap(next.tt[next.pos],next.tt[start.pos]);<br /> }<br /> }<br /> }<br /> return false;<br /> }<br /> char move2[maxn];<br /> int index;<br /> void Output()<br /> {<br /> index=0;<br /> int kk=end_state,tt,diff;<br /> while((tt=info[kk].last_state)>=0)//反演路径<br /> {<br /> diff=info[tt].pos-info[kk].pos;<br /> if(diff==3) move2[index]='u';<br /> else if(diff==1) move2[index]='l';<br /> else if(diff==-1) move2[index]='r';<br /> else if(diff==-3) move2[index]='d';<br /> else printf("/nwrong/n");<br /> index++;<br /> kk=tt;<br /> }<br /> for(int i=index-1;i>=0;i--) printf("%c",move2[i]);//输出路径<br /> printf("/n");<br /> }<br /> int main()<br /> {<br /> freopen("e://1.in","r",stdin);<br /> freopen("e://1.out","w",stdout);<br /> Init();<br /> _clr(info,-1);<br /> char for_input[5];<br /> int first=0,count=0;<br /> for(int i=0;i<9;i++)<br /> {<br /> scanf("%s",for_input);<br /> if(for_input[0]=='x') start.tt[i]=8,start.pos=i;<br /> else start.tt[i]=for_input[0]-'0'-1;<br /> }<br /> first=get_key(start.tt);<br /> if(first==end_state)<br /> {<br /> printf("/n");<br /> return 0;<br /> }<br /> info[first].last_state=-1;<br /> info[first].pos=start.pos;<br /> start.step=info[first].step=h(start.tt);<br /> start.state=first;<br /> my_queue.push(start);<br /> if(Find_path()) Output();<br /> else printf("unsolvable/n");<br /> return 0;<br /> }<br />