首页 > 代码库 > 八数码难题 题解
八数码难题 题解
题目大意：
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
思路：
典型的搜索题，做法有BFS+Hash、双向BFS、A*等，我认为A*相对好写（我比较懒）（但貌似稍微慢了一点）。每种状态的估价函数的值为现在1~8的位置与目标状态中1~8的位置一一对应后的“哈曼顿距离”（打一个比方）的和。
代码：
1 #include<cmath> 2 #include<cstdio> 3 #include<iostream> 4 using namespace std; 5 const int d[4]={-1,0,0,1},f[4]={0,-1,1,0},w[9]={2,1,1,1,2,3,3,3,2},z[9]={2,1,2,3,3,3,2,1,1}; 6 int ans=-1,flag,a[4][4]; 7 8 int guess() 9 {10 int i,j,sum=0;11 for (i=1;i<4;i++)12 for (j=1;j<4;j++)13 if (a[i][j]) sum+=abs(w[a[i][j]]-i)+abs(z[a[i][j]]-j);14 return sum;15 }16 17 void dfs(int now,int x,int y)18 {19 if (flag) return;20 if (now>ans) return;21 int v=guess(),i,m,n;22 if (v+now>ans) return;23 if (!v) { flag=1; return; }24 for (i=0;i<4;i++)25 {26 m=x+d[i],n=y+f[i];27 if (m && m<4 && n && n<4)28 {29 swap(a[x][y],a[m][n]);30 dfs(now+1,m,n);31 swap(a[x][y],a[m][n]);32 }33 }34 }35 36 int main()37 {38 int i,j,x,y;39 for (i=1;i<4;i++)40 for (j=1;j<4;j++)41 {42 a[i][j]=getchar()-48;43 if (!a[i][j]) x=i,y=j;44 }45 while (!flag) ans++,dfs(0,x,y);46 printf("%d\n",ans);47 return 0;48 }
八数码难题 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。