蓝桥杯的一道题。原题链接
我用了全排列的编码优化。
AC代码
#include<cstdio> #include<cstring> const int maxn=400000; const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; typedef int state[9]; int goal[9]; int res[maxn][9]; //存储访问过的节点 int d[maxn],fact[9]; int vis[maxn]; void init() { fact[0]=1; for(int i=1;i<9;++i) fact[i]=i*fact[i-1]; } int KT_solve(int row) //编码函数 { int code=0; for(int i=0;i<9;++i) { int cnt=0; for(int j=i+1;j<9;++j) { if(res[row][j]<res[row][i]) ++cnt; } code+=cnt*fact[8-i]; } if(vis[code]) return 0; return vis[code]=1; } int bfs() { init(); int front=1,real=2; while(front<real) { state &s=res[front]; //用"引用"简化代码 if(memcmp(goal,s,sizeof(s))==0) return front; int pos; for(pos=0;pos<9;++pos) if(!s[pos]) break; int x=pos/3,y=pos%3; for(int i=0;i<4;++i) { int newx=x+dx[i],newy=y+dy[i]; int new_pos=newx*3+newy; if(newx>=0&&newy<3&&newy>=0&&newy<3) { state &t=res[real]; //向状态数组加入新的状态 memcpy(&t,&s,sizeof(s)); t[pos]=s[new_pos]; t[new_pos]=s[pos]; d[real]=d[front]+1; if(KT_solve(real)) real++; } } front++; } return 0; } int main() { memset(vis,0,sizeof(vis)); d[1]=0; char s[10]; scanf("%s",s); for(int j=0;j<9;++j) { if(s[j]=='.') res[1][j]=0; else res[1][j]=s[j]-'0'; } scanf("%s",s); for(int j=0;j<9;++j) { if(s[j]=='.') goal[j]=0; else goal[j]=s[j]-'0'; } int ans=bfs(); if(ans>0) printf("%d\n",d[ans]); else printf("-1\n"); return 0; }如有不当之处欢迎指出！
