题目描述:题目链接
在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的 棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为 123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
输入输出格式
输入格式:输入初始状态,一行九个数字,空格用0表示
输出格式:只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入输出样例
输入样例#1:
283104765
输出样例#1:
4
问题分析:
这题是一题很经典的BFS,下面简要分析一下过程
首先题目中变换的大意是将初始数字经过转换,变成目标状态
经过分析,大致的转换过程如下:1.数字转数组,2.进行变换,3.转换完后进行数组转数字
变换过程如下:283104765->y[9]={2,8,3,1,0,4,7,6,5}
y[0]可以与y[1],y[3]交换,y[1]可以与y[0],y[2],y[4]交换
则可以将 i 可以交换的下标存储为 way[9][4] 表示 i 可以与 y[ way[i][j] ]进行交换!!!
short Way[9][4]= {{3,1},{4,0,2},{5,1},{6,0,4},{7,1,3,5},{8,2,4},{3,7},{4,6,8},{5,7}}; //每个点可行的路径 short way[9]= {2,3,2,3,4,3,2,3,2},y[9];//way存储个数
0 | 1 | 2 |
3 | 4 | 5 |
6 | 7 | 8 |
交换完成后将数组转换成数字存入队列中,进行下一个的拓展!!!
单向BFS(此种方法过于粗糙,简单浏览就好)
#include<algorithm> #include<iostream> #include<cmath> #include<map> #include<vector> #include<cstdio> #include<cstring> #include<queue> using namespace std; int Way[9][4]= {{1,3},{4,0,2},{1,5},{0,6,4},{7,1,3,5},{2,4,8},{3,7},{4,6,8},{5,7}}; //每个点可行的路径 int way[9]= {2,3,2,3,4,3,2,3,2}; struct s { int NO;//当前状态 int step=1;//步骤数 int num;//0所在位置 int from; }; int main(void) { map<long,long>m;//用于判断是否已经走过 int ANS=123804765; int T; cin>>T; queue <s> MAP; s t; int xx=T; for(int i=8; i>=0; --i) { if(xx%10==0) { t.num=i;//查找0的初始位置 break; } xx/=10; } t.NO=T; t.from=t.num; MAP.push(t); int ans=99999999; while(!MAP.empty())//BFS模板 { s temp=MAP.front(); MAP.pop(); if(m[temp.NO]==temp.step) continue; m[temp.NO]=temp.step; if(temp.NO==ANS)//找到答案 { ans=min(ans,temp.step); continue; } for(int i=0; i<way[temp.num]; ++i) { int x=Way[temp.num][i]; if(x==temp.from) continue; t=temp; t.from=temp.num; t.step++; if(t.step>=ans) continue; int str[10],ss=t.NO; for(int i=0; i<9; ++i)//数字转数组 { str[8-i]=ss%10; ss/=10; } swap(str[t.num],str[x]); t.NO =0; for(int i=0; i<9; ++i)//数组转数字 { t.NO=t.NO*10+str[i]; } t.num=x; MAP.push(t); } } cout<<ans-1; return 0; }
双向BFS
由于是寻找最少步骤,则第一次拓展出的步骤一定是最少的,那么第一次寻找到达答案的步骤即为最少!!!
此处可用上双向BFS的思想进行进一步优化!!!
#include<cstdio> #include<cstdlib> #include<iostream> #include<queue> #include<map> using namespace std; short Way[9][4]= {{3,1},{4,0,2},{5,1},{6,0,4},{7,1,3,5},{8,2,4},{3,7},{4,6,8},{5,7}}; //每个点可行的路径 short way[9]= {2,3,2,3,4,3,2,3,2},y[9]; int T=123804765,F; queue<int>Q; map<int ,int>tx; map<int ,int>step; int main(void) { scanf("%d",&F); if(F==T) //特判,可以减少许多步骤 { putchar('0'); return 0; } Q.push(F);//同时从头拓展和从尾拓展 Q.push(T); tx[T]=2,tx[F]=1,step[T]=1,step[F]=0;//初始化 while(!Q.empty()) { int t=Q.front(),z=t; Q.pop(); int num; for(int j=8; j>=0; --j) //数字转数组 { y[j]=z%10; if(y[j]==0) num=j;//寻找0 z/=10; } for(int i=0; i<way[num]; ++i) { z=0; int x=Way[num][i]; swap(y[num],y[x]); for(int j=0; j<=8; ++j) z=(z<<1)+(z<<3)+y[j];//数组转数字 if(tx[z]==tx[t])//!!!最重要的一点,由于其他步骤都是最优,则对于 同为从头开始 或 同为从尾开始的状态 就没有必要进行重复的拓展!!!这是一个最重要的优化
{ swap(y[num],y[x]);//要记得交换回去 continue; } if(tx[z]+tx[t]==3) { printf("%d",step[z]+step[t]);//输出结果 return 0;//结束程序 } step[z]=step[t]+1;//步数加一 tx[z]=tx[t];//方向传递 swap(y[num],y[x]);//记得交换回去 Q.push(z) ;//插入队列 } } return 0; }