首页 > 代码库 > 1225 八数码难题
1225 八数码难题
1225 八数码难题
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入描述 Input Description
输入初试状态，一行九个数字，空格用0表示
输出描述 Output Description
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
样例输入 Sample Input
283104765
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
详见试题
分类标签 Tags 点此展开
代码有点乱
思路还算清晰
bfs+hash判重
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 using namespace std; 5 const int MAXN=5; 6 int xx[5]={-1,+1,0,0}; 7 int yy[5]={0,0,-1,+1}; 8 struct node 9 { 10 int mp[MAXN][MAXN]; 11 }a[100001]; 12 int hashfind[3733801]; 13 int step[200]; 14 int h=0,t=1; 15 int bc[MAXN][MAXN]={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}}; 16 int hash() 17 { 18 int s=0; 19 int k=1; 20 for(int i=1;i<=3;i++) 21 { 22 for(int j=1;j<=3;j++) 23 { 24 s=s+a[t].mp[i][j]*k; 25 k=k*7; 26 } 27 } 28 s=s%3733801; 29 if(hashfind[s]==0) 30 { 31 hashfind[s]=1; 32 return 1; 33 } 34 else 35 { 36 return 0; 37 } 38 } 39 int check() 40 { 41 for(int i=1;i<=3;i++) 42 { 43 for(int j=1;j<=3;j++) 44 { 45 if(a[t].mp[i][j]!=bc[i][j]) 46 return 0; 47 } 48 } 49 return 1; 50 } 51 void move(int x,int y) 52 { 53 54 for(int i=0;i<4;i++) 55 { 56 int wx=x+xx[i]; 57 int wy=y+yy[i]; 58 if(wx>=1&&wx<=3&&wy>=1&&wy<=3) 59 { 60 for(int j=1;j<=3;j++) 61 { 62 for(int k=1;k<=3;k++) 63 { 64 a[t].mp[j][k]=a[h].mp[j][k]; 65 } 66 } 67 swap(a[t].mp[wx][wy],a[t].mp[x][y]); 68 step[t]=step[h]+1; 69 if(check()==1) 70 { 71 printf("%d",step[t]); 72 exit(0);// end 73 } 74 if(hash()==1) 75 t++; 76 } 77 } 78 } 79 void bfs() 80 { 81 while(h<t) 82 { 83 for(int i=1;i<=3;i++) 84 { 85 for(int j=1;j<=3;j++) 86 { 87 if(a[h].mp[i][j]==0) 88 { 89 move(i,j); 90 } 91 } 92 } 93 h++; 94 } 95 } 96 int main() 97 { 98 char dr[10]; 99 int bgx=0;100 int bgy=0;101 gets(dr);102 int now=0;103 for(int i=1;i<=3;i++)104 {105 for(int j=1;j<=3;j++)106 {107 a[0].mp[i][j]=dr[now]-48;108 if(a[0].mp[i][j]==0)109 {110 bgx=i;111 bgy=j;112 }113 now++;114 }115 }116 bfs();117 return 0;118 }
1225 八数码难题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。