【一只蒟蒻的刷题历程】【蓝桥杯】历届试题 九宫重排 （八数码问题：BFS+集合set）

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。 我们把第一个图的局面记为：12345678. 把第二个图的局面记为：123.46758 显然是按从上到下，从左到右的顺序记录数字，空格记为句点。 本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入格式

输入第一行包含九宫的初态，第二行包含九宫的终态。

输出格式

输出最少的步数，如果不存在方案，则输出-1。

样例输入

样例输出

3

样例输入

样例输出

22

---

思路：

思路来自紫书P199页，一毛一样的题目。

通过BFS求最短路，第一次出现与目标九宫格相同时，就是最少的步数

把九宫格的状态通过数组记录下来，记录过程中需要判重，避免把同种情况的九宫格访问多次。

判重：将九宫格变化为一个九位数放入集合中（集合中没有才放入）。

看书上说集合这种方法虽然简单，但是效率最慢，以后有需要在学习其他几种方法。

memcmp memcpy

代码：

#include <iostream> #include <algorithm> #include <string> #include <queue> #include <cstring> #include <cmath> #include <vector> #include <set> #include <map> using namespace std; typedef int state[9]; string s1,s2; const int maxn=362900; //最大情况9！=362880 state st[maxn],goal; //存过程的二维数组和目标数组，st相当于st[maxn][9] set<int> s; //集合 int dis[maxn]; //距离 int dx[]={0,0,1,-1}; //四个方向 int dy[]={1,-1,0,0}; void init() {s.clear();} //初始化集合 bool insert(int rear) //插入集合 { int v=0; for(int i=0;i<9;i++) v=v*10+st[rear][i]; //九宫格转变为九位数 if(s.count(v)>0) return 0; //s中有相同的，return 0 s.insert(v); return 1; } int bfs() { init(); int front=1,rear=2; //如果要从0开始，最后可以用return -1表示不存在 while(front<rear) { state& f = st[front]; //引用 if(memcmp(goal,f,sizeof(f))==0) return front; //比较数组 int z; for(z=0;z<9;z++) if(!f[z]) break; //找0的位置 int x=z/3,y=z%3; //行列编号 for(int i=0;i<4;i++) { int newx=x+dx[i]; int newy=y+dy[i]; int newz=3*newx+newy; //在一维数组中的下标 if(newx>=0&&newx<3&&newy>=0&&newy<3) { state& r= st[rear]; //引用 memcpy(r,f,sizeof(f)); //扩展新节点(先和上一个状态一样) r[newz]=f[z]; //然后改变移动以后，变化的两个点 r[z]=f[newz]; dis[rear]=dis[front]+1; //更新步数 if(insert(rear)) rear++; //插入成功，队尾往后移 } } front++; //扩展完毕后修改队首指针 } return 0; //不存在 } int main() { getline(cin,s1); //字符串输入，再转化为int数组 getline(cin,s2); for(int i=0;i<9;i++) { if(s1[i]=='.') st[1][i]=0; //起始状态 else st[1][i]=s1[i]-'0'; if(s2[i]=='.') goal[i]=0; //目标状态 else goal[i]=s2[i]-'0'; } int ans = bfs(); if(!ans) cout<<-1; else cout<<dis[ans]; return 0; }