推箱子问题的设计与实现(共5页).doc

《推箱子问题的设计与实现(共5页).doc》由会员分享，可在线阅读，更多相关《推箱子问题的设计与实现(共5页).doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上推箱子问题的设计与实现实验报告班级：计本四班 学号： 姓名：刘宝同一、问题描述码头仓库是划分为 nm个格子的矩形阵列。有公共边的格子是相邻格子。当前仓库中有的格子是空闲的；有的格子则已经堆放了沉重的货物。由于堆放的货物很重，单凭仓库管理员的力量是无法移动的。仓库管理员有一项任务，要将一个小箱子推到指定的格子上去。管理员可以在仓库中移动，但不能跨过已经堆放了货物的格子。管理员站在与箱子相对的空闲格子上时，可以做一次推动，把箱子推到另一相邻的空闲格子。推箱时只能向管理员的对面方向推。由于要推动的箱子很重，仓库管理员想尽量减少推箱子的次数。二、问题求解分析对于给定的仓库布局

2、，以及仓库管理员在仓库中的位置和箱子的开始位置和目标位置，设计一个解推箱子问题的分支限界法，计算出仓库管理员将箱子从开始位置推到目标位置所需的最少推动次数。数据输入：由文件 input.txt 提供输入数据。输入文件第1行有2个正整数 n 和 m（1=n,m=100），表示仓库是 nm个格子的矩形阵列。接下来有 n 行，每行有 m个字符，表示格子的状态。S 表示格子上放了不可移动的沉重货物；w 表示格子空闲；M 表示仓库管理员的初始位置；P 表示箱子的初始位置；K 表示箱子的目标位置。结果输出:将计算出的最少推动次数输出到文件 output.txt。如果仓库管理员无法将箱子从开始位置推到目标位

3、置则输出“No solution！”。三、源程序关键代码专心-专注-专业#include #include #include int map1(int a910);char move(char t,int map910)int i,j,x,y;system(CLS); /清屏for(i=0;i9;i+) / 查找当前人位置for(j=0;j10;j+)if(mapij=4 | mapij=6)x=i,y=j;switch(t)case 8: if(mapx-1y=1)/如果人面前时路 mapx-1y=4; if(mapxy=4) mapxy=1;else mapxy=2;else if(map

4、x-1y=3)/人面前是箱子if(mapx-2y=2)/ 人前箱子 箱子前面是空位mapx-1y=4;mapx-2y=5;if(mapxy=4) mapxy=1;else mapxy=2;else if(mapx-2y=0 | mapx-2y=3 | mapx-2y=5)/人前是箱子 箱子前面是墙 箱子 已在空位上的箱子printf(a); else if(mapx-2y=1)/ 人前是箱子 箱子前面是路mapx-1y=4;mapx-2y=3;if(mapxy=4) mapxy=1; else mapxy=2; else if(mapx-1y=0) /人前是墙 printf(a); else

5、if(mapx-1y=2) mapx-1y=6; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapx-1y=5)/人前是已在空位的箱子 if(mapx-2y=2)/人前是已在空位是的箱子 箱子前是一个空位 mapx-1y=6;mapx-2y=5;if(mapxy=4) mapxy=1; else mapxy=2; else if(mapx-2y=0 | mapx-2y=3 | mapx-2y=5)/人前是已在空位是的箱子 箱子前是墙 箱子 已在空位上的箱子 printf(a); else if(mapx-2y=1)/人前是已在空位上的箱子 箱子前是路

6、 mapx-1y=6;mapx-2y=3;if(mapxy=4) mapxy=1; else mapxy=2; ;break;case 6: if(mapxy+1=1)/如果人面前时路 mapxy+1=4; if(mapxy=4) mapxy=1; else mapxy=2;else if(mapxy+1=3)/人面前是箱子if(mapxy+2=2)/ 人前箱子 箱子前面是空位 mapxy+1=4;mapxy+2=5; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapxy+2=0 | mapxy+2=3 | mapxy+2=5)/人前是箱子 箱子前面

7、是墙 箱子 已在空位上的箱子 printf(a); else if(mapxy+2=1)/ 人前是箱子 箱子前面是路 mapxy+1=4;mapxy+2=3; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapxy+1=0) /人前是墙 printf(a); else if(mapxy+1=2) mapxy+1=6; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapxy+1=5)/人前是已在空位的箱子 if(mapxy+2=2)/人前是已在空位是的箱子 箱子前是一个空位 mapxy+1=6;mapxy+2=5

8、; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapxy+2=0 | mapxy+2=3 | mapxy+2=5)/人前是已在空位是的箱子 箱子前是墙 箱子 已在空位上的箱子 printf(a); else if(mapxy+2=1)/人前是已在空位上的箱子 箱子前是路 mapxy+1=6;mapxy+2=3; if(mapxy=4) mapxy=1; else mapxy=2; ;break; case 2: if(mapx+1y=1)/如果人面前时路 mapx+1y=4; if(mapxy=4) mapxy=1; else mapxy=2;els

9、e if(mapx+1y=3)/人面前是箱子if(mapx+2y=2)/ 人前箱子 箱子前面是空位 mapx+1y=4;mapx+2y=5; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapx+2y=0 | mapx+2y=3 | mapx+2y=5)/人前是箱子 箱子前面是墙 箱子 已在空位上的箱子 printf(a); else if(mapx+2y=1)/ 人前是箱子 箱子前面是路 mapx+1y=4;mapx+2y=3; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapx+1y=0) /人前是墙 p

10、rintf(a); else if(mapx+1y=2) mapx+1y=6; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapx+1y=5)/人前是已在空位的箱子 if(mapx+2y=2)/人前是已在空位是的箱子 箱子前是一个空位 mapx+1y=6;mapx+2y=5; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapx+2y=0 | mapx+2y=3 | mapx+2y=5)/人前是已在空位是的箱子 箱子前是墙 箱子 已在空位上的箱子 printf(a); else if(mapx+2y=1)/人

11、前是已在空位上的箱子 箱子前是路 mapx+1y=6;mapx+2y=3; if(mapxy=4) mapxy=1; else mapxy=2; ;break;case 4: if(mapxy-1=1)/如果人面前时路 mapxy-1=4; if(mapxy=4) mapxy=1; else mapxy=2;else if(mapxy-1=3)/人面前是箱子if(mapxy-2=2)/ 人前箱子 箱子前面是空位 mapxy-1=4;mapxy-2=5; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapxy-2=0 | mapxy-2=3 | mapx

12、y-2=5)/人前是箱子 箱子前面是墙 箱子 已在空位上的箱子 printf(a); else if(mapxy-2=1)/ 人前是箱子 箱子前面是路 mapxy-1=4;mapxy-2=3; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapxy-1=0) /人前是墙 printf(a); else if(mapxy-1=2) mapxy-1=6; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapxy-1=5)/人前是已在空位的箱子 if(mapxy-2=2)/人前是已在空位是的箱子 箱子前是一个空位 ma

13、pxy-1=6;mapxy-2=5; if(mapxy=4) mapxy=1; else mapxy=2; else if(mapxy-2=0 | mapxy-2=3 | mapxy-2=5)/人前是已在空位是的箱子 箱子前是墙 箱子 已在空位上的箱子 printf(a); else if(mapxy-2=1)/人前是已在空位上的箱子 箱子前是路 mapxy-1=6;mapxy-2=3; if(mapxy=4) mapxy=1; else mapxy=2; ;break;map1(map);return (map910);int map1(int a910)int i,j;static int

14、 count=0;system(cls);printf(nnttt 欢迎选玩*【推箱子游戏】O(_)O nnttttt 游戏规则： ntt :代表墙 ：代表路 ：代表空位ntt ：代表箱子 ：代表人 ：代表箱子已在空位上nttttt 8:向上移动nttttt 2:向下移动nttttt 4:向左移动nttttt 6:向右移动nttttt) ;for(i=0;i9;i+)printf(ntttt ); for(j=0;j10;j+) switch(aij) case 0: printf();break;/代表墙 case 1: printf();break;/代表路 case 2: printf(

15、);break;/代表空位 case 3: printf();break;/代表箱子 case 4: printf();break;/代表人 case 5:printf();break;/代表箱子已在空位上 case 6: printf();break;printf(ntttt步数：%d,count+);printf(ntttt);return (a910);int main()char c;int map910= 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,2,1,0,0,0,0,1,3,2,3,3,3,1,1,0,0,1,0,1,0,2,1,0,1,0,0,1,4,2,1,

16、2,1,0,1,0,0,0,0,0,1,3,1,1,1,0,0,0,0,0,3,2,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0; system(color E9); map1(map); while(1) c=getch(); if(c=8 | c=6 | c=2 | c=4) move(c,map);四、总结通过对推箱子游戏的编程和设计，进一步巩固了数据结构和算法设计与分析所学的知识，在查阅了有关推箱子游戏问题编程的相关知识的同时，也进一步了解了结构体之间的密切关系，并加深和巩固了函数调用的方法和技巧。同时，也了解到自我知识体系的不足。在实验编程中，出现很多问题，如将函数的形参和实参混淆等，这些问题最终在老师的帮助下成功解决，并成功运行。五、参考文献1 马安鹏.Visual C+程序设计导学。北京：清华大学出版社，20022谭浩强，C程序设计（第三版）。北京：清华大学出版社，2005（2007重印）