类似于八数码的一道经典搜索题,思路基本也一样.我是用康拓展开进行的判重.
代码如下:
/*ID: 15674811LANG: C++TASK: msquare*/;{int a[9];int cnt,flag;}S;S st[maxn],goal;int fa[maxn],vis[maxn],fac[10];char ch[]={‘A’,’B’,’C’};char ans[maxn];int Hash(S s1){int code=0;for(int i=1;i<9;i++){int cnt=0;for(int j=i+1;j<9;j++)if(s1.a[j]<s1.a[i]) cnt++;code+=fac[8-i]*cnt;}return code;}S change(int x,S st){if(x==0){for(int i=1;i<=4;i++)swap(st.a[i],st.a[8-i+1]);}if(x==1){int k=st.a[4];for(int i=4;i>1;i–)st.a[i]=st.a[i-1];st.a[1]=k;k=st.a[5];for(int i=5;i<8;i++)st.a[i]=st.a[i+1];st.a[8]=k;}if(x==2){int k=st.a[3];st.a[3]=st.a[2];int k1=st.a[6];st.a[6]=k; k=k1;k1=st.a[7]; st.a[7]=k;st.a[2]=k1;}st.cnt=st.cnt+1;st.flag=x;return st;}int check(S s1){for(int i=1;i<=8;i++)if(s1.a[i]!=goal.a[i])return 0;return 1;}int bfs(){vis[Hash(st[0])]=1;int front=0,rear=1;while(front<rear){S s1=st[front];if(check(s1))return front;for(int i=0;i<3;i++){S s=change(i,s1);int k=Hash(s);if(vis[k]) continue;vis[k]=1;st[rear]=s;fa[rear]=front;++rear;}++front;}}void Init(){for(int i=1;i<=maxn;i++)fa[i]=i;memset(vis,0,sizeof(vis));for(int i=1;i<=8;i++)st[0].a[i]=i;st[0].cnt=0;}void print(int x){int cnt=st[x].cnt;int k=0;while(1){if(x==0) break;ans[k++]=ch[st[x].flag];x=fa[x];}printf(“%d\n”,cnt);int j=0;for(int i=k-1;i>=0;i–){printf(“%c”,ans[i]);j++;if(j%60==0&&i!=0)printf(“\n”);}printf(“\n”);}int main(){freopen(“msquare.in”,”r”,stdin);freopen(“msquare.out”,”w”,stdout);//freopen(“in.txt”,”r”,stdin);fac[0]=1;for(int i=1;i<=8;i++) fac[i]=fac[i-1]*i;for(int i=1;i<=8;i++)scanf(“%d”,&goal.a[i]);Init();int x=bfs();print(x); return 0;}
，贪婪是最真实的贫穷，满足是最真实的财富
