#include<cstdio> #include<cstring> using namespace std; typedef int state[9]; const int maxn = 10000000; state st[maxn],goal; int dist[maxn]; int fact[9]; int vis[maxn]; void init(){ fact[0]=1; for(int i=1;i<9;i++) fact[i]=i*fact[i-1]; } int try_to_insert(int s){ int code = 0 ; for(int i=0;i<9;i++){ int cnt =0; for(int j=i+1;j<9;j++) if(st[s][j]<st[s][i]) cnt++; code += fact[8-i] * cnt ; } if(vis[code]) return 0; vis[code]=1; return 1; } const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0}; int dfs(){ init(); int front = 1 , rear = 2; while( front < rear ){ state &s = st[front]; if(memcmp(s,goal,sizeof(goal))==0) return front ; int z ; for(z=0;z<9;z++) if(!s[z]) break; int x=z/3; int y=z%3; for(int d=0;d<4;d++){ int newx=x+dx[d]; int newy=y+dy[d]; int newz=newx*3+newy; if(newx>=0 && newx<3 &&newy>=0 && newy <3){ state &t=st[rear]; memcpy(&t,&s,sizeof(s)); t[newz]=s[z]; t[z]=s[newz]; dist[rear]=dist[front]+1; if(try_to_insert(rear)) rear++; } } front++; } } int main(void){ char s1[10],s2[10]; scanf("%s%s",s1,s2); for(int i=0;i<9;i++){ if(s1[i]!='.') st[1][i]=s1[i]-'0'; else st[1][i]=0; if(s2[i]!='.') goal[i]=s2[i]-'0'; else goal[i]=0; } int ans=dfs(); if(ans) printf("%d\n",dist[ans]); else printf("%d\n",-1); return 0; }
解题思路:
注意事项:
参考代码:
0.0分
7 人评分
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C语言代码)浏览:1078 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:506 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:994 |
简单的a+b (C++语言代码)浏览:894 |
输出正反三角形 (C语言代码)浏览:856 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 (C语言代码)浏览:755 |
蛇行矩阵 (C语言代码)浏览:601 |
DNA (C语言描述,蓝桥杯)浏览:1648 |
青年歌手大奖赛_评委会打分 (C语言代码)浏览:2238 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:588 |