历届试题 九宫重排 (bfs 康托判重) 迈不过友情╰ 2022-06-18 08:20 152阅读 0赞 问题描述 如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。 ![RequireFile.do_fid_qYebaGed][] ![RequireFile.do_fid_HQ3JFM72][] 我们把第一个图的局面记为:12345678. 把第二个图的局面记为:123.46758 显然是按从上到下,从左到右的顺序记录数字,空格记为句点。 本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1。 输入格式 输入第一行包含九宫的初态,第二行包含九宫的终态。 输出格式 输出最少的步数,如果不存在方案,则输出-1。 样例输入 12345678. 123.46758 样例输出 3 样例输入 13524678. 46758123. 样例输出 22 这道题在寒假的时候就想做了,但那时候啥都不会,现在终于自己写出来,算是把寒假时候的愿望实现了.上午写的[2\*3格子移字母][2_3] 和这个也类似 #include<iostream> #include<string.h> #include<cstdio> #define M 1000000 using namespace std; typedef int type[9]; type qs,mb,gc[M]; int sept[M]; //保存步数 int dir[4][2] = {-1,0,0,-1,0,1,1,0},st=0; int step[M]={0}; int fact[10]={1},vis[M]; void init() //初始化 阶乘 { int i; for (i=1; i<=9; i++) { fact[i] = i*fact[i-1]; } } int kangtuo(int *a) { int num=0,t,i,j; for (i=0; i<8; i++) { t = 0; for (j=i+1; j<9; j++) { if (a[i] > a[j]) t++; } num += t * fact[8-i];//num为展开的第几个排列 } if (vis[num] == 1) return 0; vis[num] = 1; return 1; } int bfs() { int front=0,rear=1,i,j,k,c,x,y,xx,yy; memcpy(gc[st],qs,sizeof(qs)); //把起始状态放入 while (front < rear) { type temp; memcpy(temp,gc[front],sizeof(gc[front])); //获取对头 if (memcmp(temp,mb,sizeof(mb))==0)//到达终点 { return front; } for(k=0; k<9; k++) { if (temp[k]==0) break; } x = k/3; y = k%3; //转2维下标 for(i=0; i<4; i++) { xx = dir[i][0] + x; yy = dir[i][1] + y; if (xx>=0&&yy>=0&&xx<3&&yy<3) { c = 3*xx + yy; type temp2; memcpy(temp2,temp,sizeof(temp)); temp2[k] = temp2[c]; temp2[c] = 0; //进行交换 if (kangtuo(temp2))//康托展开 ,判重 { memcpy(gc[rear],temp2,sizeof(temp2)); step[rear++] = step[front] + 1; } } } front++;//进入下一个队列元素 } return -1; } int main() { char ch; int i,r; init(); for (i=0; i<9; i++) { cin>>ch; ch == '.' ? qs[i]=0 : qs[i]=ch-'0'; } getchar(); for (i=0 ;i<9; i++) { cin>>ch; ch == '.' ? mb[i]=0 : mb[i]=ch-'0'; } r = bfs(); r == -1 ? cout<<r<<endl : cout<<step[r]<<endl; return 0; } [RequireFile.do_fid_qYebaGed]: http://lx.lanqiao.cn/RequireFile.do?fid=qYebaGed [RequireFile.do_fid_HQ3JFM72]: http://lx.lanqiao.cn/RequireFile.do?fid=HQ3JFM72 [2_3]: http://blog.csdn.net/qq_36238595/article/details/68944498
还没有评论,来说两句吧...