历届试题 九宫重排 (bfs 八数码问题) 柔光的暖阳◎ 2022-07-04 21:28 152阅读 0赞 问题描述 如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。 ![RequireFile.do_fid_qYebaGed][] ![RequireFile.do_fid_HQ3JFM72][] 我们把第一个图的局面记为:12345678. 把第二个图的局面记为:123.46758 显然是按从上到下,从左到右的顺序记录数字,空格记为句点。 本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1。 输入格式 输入第一行包含九宫的初态,第二行包含九宫的终态。 输出格式 输出最少的步数,如果不存在方案,则输出-1。 样例输入 12345678. 123.46758 样例输出 3 样例输入 13524678. 46758123. 样例输出 22 这题困扰我很久 网站找了些八数码的代码看看,什么哈希太深奥了,看不懂阿,后来找到了一段比较好理解的 代码: #include "iostream" #include "algorithm" #include "vector" #include "set" #include "string.h" #include "ctype.h" #define M 1000000 using namespace std; typedef int type[9]; type qs[M]; type mb; int front,rear; int dir[4][2]={-1,0,0,-1,0,1,1,0}; int dis[M]={0}; set<int> vis; //容器,存储不同的值 int panchong(int x) { int i,sum=0; for (i=0; i<9; i++) { sum = sum*10+qs[x][i]; } if (vis.count(sum)) //容器中有相同 { return 0; } vis.insert(sum);//插入容器 return 1; } int bfs() { front = 1; rear = 2; int i,j,k=0,c,x,y,xx,yy; while (front < rear) { type &s = qs[front]; //s指向qs[front] if (memcmp(s,mb,sizeof(mb)) == 0) { return front; } for (k=0; k<9; k++) { if (s[k]==0) break; } x = k/3; y = k%3; // 转成二维数组 for (i=0; i<4; i++) { xx = x+dir[i][0]; yy = y+dir[i][1]; if(xx>=0 && xx<3 && yy>=0 && yy<3) { type &t = qs[rear];//t指向qs[rear] memcpy(t,s,sizeof(s)); t[k] = s[xx*3+yy]; //交换空格与数字位置 t[xx*3+yy] = s[k]; if (panchong(rear))//得到新的图进行判断重复 { dis[rear] = dis[front]+1; rear++; } } } front++; } return -1; } int main() { int i,j,cnt; char ch[10],ch2[10]; scanf("%s%s",ch,ch2); for (i=0; i<9; i++) { ch[i]<='8'&&ch[i]>='0' ? qs[1][i]=ch[i]-'0' : qs[1][i]=0; } for (i=0; i<9; i++) { ch2[i]<='8'&&ch2[i]>='0' ? mb[i]=ch2[i]-'0' : mb[i]=0; } cnt = bfs(); if(cnt>0) { cout<<dis[cnt]<<endl; } else { cout<<-1<<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
还没有评论,来说两句吧...