1225 八数码难题
题目描述 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 点此展开
广搜+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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-05-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录