1225 八数码难题
2018-06-17 22:40:40来源:未知 阅读 ()
Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述
在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
输入初试状态,一行九个数字,空格用0表示
只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
283104765
4
详见试题
分类标签 Tags 点此展开
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:田忌赛马
下一篇:P1115 最大子段和
- 中国象棋 2019-08-16
- BFS(五):八数码难题 (POJ 1077) 2019-08-16
- UVA 1225 Digit Counting(c++)(模拟) 2018-07-23
- 关于51单片机数码管消影 2018-06-18
- 毕业回馈-89C51之数码管的使用 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash