题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入输出格式
输入格式：
输入初始状态，一行九个数字，空格用0表示
输出格式：
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入输出样例
输入样例1：
283104765
输出样例1：
4
思路：
bfs，我们首先要找到空格即0所在的位置，然后向四个方向扩展，如果目标状态没有访问过，那就转移到目标状态，然后加入队列中。之后使用map去重，我们把每一个状态都转化成一个哈希值，如果访问了就将其设成1，如果目标哈希值等于123804765，即找到了最少转换次数。
代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<queue> #include<map> using namespace std; static int n=9; static int dx[5]={0,0,1,0,-1},dy[5]={0,-1,0,1,0}; map < long long , bool > vis;//去重 struct Mt{ int a[5][5]; int s,num; }; Mt be; queue < Mt > q; static int ex(Mt x)//计算哈希值 { int y=9,ans=0; for(int i=1;i<=3;++i) for(int j=1;j<=3;++j) ans+=x.a[i][j]*pow(10,--y); return ans; } static int bfs(Mt x) { q.push(x);//将初始状态加入队列 vis[ex(x)]=1;//当前状态已经被访问过，设为1 while(!q.empty()) { Mt u=q.front();q.pop();//取出队首元素 if(u.s==123804765)//如果搜到了初始状态，输出次数，return 0 { printf("%d",u.num); return 0; } for(int i=1;i<=3;++i) for(int j=1;j<=3;++j)//寻找当前0的位置 { if(u.a[i][j]==0)//找到 { for(int k=1;k<=4;++k)//枚举四个方向 { if(i+dx[k]>=1&&i+dx[k]<=3&&j+dy[k]>=1&&j+dy[k]<=3)//如果没有超过临界范围 { int nx=i+dx[k],ny=j+dy[k],cg_num;//记录目标坐标 Mt v=u;//u是当前状态，v是目标状态 v.a[i][j]=v.a[nx][ny];//同下 v.a[nx][ny]=0;//交换位置 v.num=u.num+1;//记录次数+1 v.s=ex(v);//计算当前状态哈希值 if(!vis[v.s])//入队操作 { q.push(v); vis[v.s]=1; } } } } else continue; } } } int main() { for(int i=1;i<=3;++i) for(int j=1;j<=3;++j) { char ch=getchar(); be.a[i][j]=ch-'0';//读入 } be.s=ex(be);be.num=0;//将当前状态转为哈希值，并且初始化操作次数 bfs(be);//搜索 return 0; }