❓问题描述
[蓝桥杯][历届试题]九宫重排
时间限制: 1Sec 内存限制: 128MB 提交: 586 解决: 126
题目描述
如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。
网络异常，图片无法展示|
编辑网络异常，图片无法展示|我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
输入
输入第一行包含九宫的初态，第二行包含九宫的终态。
输出
输出最少的步数，如果不存在方案，则输出-1。
样例输入
12345678. 123.46758
样例输出
3
提示
💡思路
把此类问题看成 寻最短路径问题，相当于空白格相当于起点，然后找到空白格从开始图的位置到最后目标图的位置且图中数字 相同的最小步数。
寻找最小步数 ，可以用BFS来实现，涉及到状态压缩 和 查重 这里我们可以借助一个map映射
（将字符状态映射为一个int型的整数 比如 12345678. ----> 98 别管这个值怎么来的 反正 每个状态 可以映射为唯一的一个整数值）来标记是否这个界面已经被访问过。或则自己写一个哈希来存状态。
AC代码：
usingnamespacestd; charstart[4][4],goal[4][4]; intdf[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; map<string,int>vis; structNode{ intx,y; longlongstep; charMap[4][4]; }; boolcheck_g(Nodea)///判断这个图和目标图是否相同{ for(inti=1;i<=3;i++) for(intj=1;j<=3;j++) if(a.Map[i][j]!=goal[i][j])returnfalse; returntrue; } boolcheck_cf(Nodea)///判断这个局面是否出现过{ strings=""; for(inti=1;i<=3;i++) for(intj=1;j<=3;j++)s+=a.Map[i][j]; if(vis[s]>0)returnfalse; vis[s]++; returntrue; } intBFS(intx1,inty1)///BFS寻找最少步数{ Nodecur,next; cur.x=x1;cur.y=y1; cur.step=0; for(inti=1;i<=3;i++) for(intj=1;j<=3;j++) cur.Map[i][j] =start[i][j];//复制一份状态queue<Node>Q;//创建一个队列Q.push(cur); //加入队列if(check_g(cur)) returncur.step;//检查是否为目标状态while(!Q.empty()){ cur=Q.front(); Q.pop(); // 出队列for(inti=0;i<4;i++){ next.x=cur.x+df[i][0]; next.y=cur.y+df[i][1]; for(inti1=1;i1<=3;i1++) for(intj=1;j<=3;j++) next.Map[i1][j]=cur.Map[i1][j];//复制一份状态next.step=cur.step+1;//当前 步数加一if(next.x>=1&&next.x<=3&&next.y>=1&&next.y<=3){//边界内swap(next.Map[next.x][next.y],next.Map[cur.x][cur.y]);///交换两个方格的位置；if(check_cf(next)){//检查重复if(check_g(next)) returnnext.step;//检查是否为目标状态Q.push(next);//入队列 } } } } return-1; } intmain() { intx1,y1; for(inti=1;i<=3;i++) for(intj=1;j<=3;j++){ cin>>start[i][j]; if(start[i][j]=='.') x1=i,y1=j;///记录空白格的位置 } for(inti=1;i<=3;i++) for(intj=1;j<=3;j++) cin>>goal[i][j]; cout<<BFS(x1,y1)<<endl; return0; }
题目链接：蓝桥杯历届试题-九宫重排 - C语言网
