推箱子问题的设计与实现

《推箱子问题的设计与实现》实验报告班级：计本四班学号：2012020386姓名：刘宝同一、问题描述码头仓库是划分为n×m个格子的矩形阵列。有公共边的格子是相邻格子。当前仓库中有的格子是空闲的；有的格子则已经堆放了沉重的货物。由于堆放的货物很重，单凭仓库管理员的力量是无法移动的。仓库管理员有一项任务，要将一个小箱子推到指定的格子上去。管理员可以在仓库中移动，但不能跨过已经堆放了货物的格子。管理员站在与箱子相对的空闲格子上时，可以做一次推动，把箱子推到另一相邻的空闲格子。推箱时只能向管理员的对面方向推。由于要推动的箱子很重，仓库管理员想尽量减少推箱子的次数。二、问题求解分析对于给定的仓库布局，以及仓库管理员在仓库中的位置和箱子的开始位置和目标位置，设计一个解推箱子问题的分支限界法，计算出仓库管理员将箱子从开始位置推到目标位置所需的最少推动次数。数据输入：由文件input.txt提供输入数据。输入文件第1行有2个正整数n和m（1=n,m=100），表示仓库是n×m个格子的矩形阵列。接下来有n行，每行有m个字符，表示格子的状态。S表示格子上放了不可移动的沉重货物；w表示格子空闲；M表示仓库管理员的初始位置；P表示箱子的初始位置；K表示箱子的目标位置。结果输出:将计算出的最少推动次数输出到文件output.txt。如果仓库管理员无法将箱子从开始位置推到目标位置则输出“Nosolution！”。三、源程序关键代码#includestdio.h#includestdlib.h#includeconio.hintmap1(inta[9][10]);charmove(chart,intmap[9][10]){inti,j,x,y;system(CLS);//清屏for(i=0;i9;i++)//查找当前人位置{for(j=0;j10;j++)if(map[i][j]==4||map[i][j]==6){x=i,y=j;};}switch(t){case'8':{if(map[x-1][y]==1)//如果人面前时路{map[x-1][y]=4;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x-1][y]==3)//人面前是箱子{if(map[x-2][y]==2)//人前箱子箱子前面是空位{map[x-1][y]=4;map[x-2][y]=5;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x-2][y]==0||map[x-2][y]==3||map[x-2][y]==5)//人前是箱子箱子前面是墙箱子已在空位上的箱子{printf(\a);}elseif(map[x-2][y]==1)//人前是箱子箱子前面是路{map[x-1][y]=4;map[x-2][y]=3;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;};}elseif(map[x-1][y]==0)//人前是墙{printf(\a);}elseif(map[x-1][y]==2){map[x-1][y]=6;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x-1][y]==5)//人前是已在空位的箱子{if(map[x-2][y]==2)//人前是已在空位是的箱子箱子前是一个空位{map[x-1][y]=6;map[x-2][y]=5;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x-2][y]==0||map[x-2][y]==3||map[x-2][y]==5)//人前是已在空位是的箱子箱子前是墙箱子已在空位上的箱子{printf(\a);}elseif(map[x-2][y]==1)//人前是已在空位上的箱子箱子前是路{map[x-1][y]=6;map[x-2][y]=3;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;};};};break;case'6':{if(map[x][y+1]==1)//如果人面前时路{map[x][y+1]=4;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x][y+1]==3)//人面前是箱子{if(map[x][y+2]==2)//人前箱子箱子前面是空位{map[x][y+1]=4;map[x][y+2]=5;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x][y+2]==0||map[x][y+2]==3||map[x][y+2]==5)//人前是箱子箱子前面是墙箱子已在空位上的箱子{printf(\a);}elseif(map[x][y+2]==1)//人前是箱子箱子前面是路{map[x][y+1]=4;map[x][y+2]=3;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;};}elseif(map[x][y+1]==0)//人前是墙{printf(\a);}elseif(map[x][y+1]==2){map[x][y+1]=6;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x][y+1]==5)//人前是已在空位的箱子{if(map[x][y+2]==2)//人前是已在空位是的箱子箱子前是一个空位{map[x][y+1]=6;map[x][y+2]=5;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x][y+2]==0||map[x][y+2]==3||map[x][y+2]==5)//人前是已在空位是的箱子箱子前是墙箱子已在空位上的箱子{printf(\a);}elseif(map[x][y+2]==1)//人前是已在空位上的箱子箱子前是路{map[x][y+1]=6;map[x][y+2]=3;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;};};};break;case'2':{if(map[x+1][y]==1)//如果人面前时路{map[x+1][y]=4;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x+1][y]==3)//人面前是箱子{if(map[x+2][y]==2)//人前箱子箱子前面是空位{map[x+1][y]=4;map[x+2][y]=5;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x+2][y]==0||map[x+2][y]==3||map[x+2][y]==5)//人前是箱子箱子前面是墙箱子已在空位上的箱子{printf(\a);}elseif(map[x+2][y]==1)//人前是箱子箱子前面是路{map[x+1][y]=4;map[x+2][y]=3;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;};}elseif(map[x+1][y]==0)//人前是墙{printf(\a);}elseif(map[x+1][y]==2){map[x+1][y]=6;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x+1][y]==5)//人前是已在空位的箱子{if(map[x+2][y]==2)//人前是已在空位是的箱子箱子前是一个空位{map[x+1][y]=6;map[x+2][y]=5;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x+2][y]==0||map[x+2][y]==3||map[x+2][y]==5)//人前是已在空位是的箱子箱子前是墙箱子已在空位上的箱子{printf(\a);}elseif(map[x+2][y]==1)//人前是已在空位上的箱子箱子前是路{map[x+1][y]=6;map[x+2][y]=3;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;};};};break;case'4':{if(map[x][y-1]==1)//如果人面前时路{map[x][y-1]=4;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x][y-1]==3)//人面前是箱子{if(map[x][y-2]==2)//人前箱子箱子前面是空位{map[x][y-1]=4;map[x][y-2]=5;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x][y-2]==0||map[x][y-2]==3||map[x][y-2]==5)//人前是箱子箱子前面是墙箱子已在空位上的箱子{printf(\a);}elseif(map[x][y-2]==1)//人前是箱子箱子前面是路{map[x][y-1]=4;map[x][y-2]=3;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;};}elseif(map[x][y-1]==0)//人前是墙{printf(\a);}elseif(map[x][y-1]==2){map[x][y-1]=6;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x][y-1]==5)//人前是已在空位的箱子{if(map[x][y-2]==2)//人前是已在空位是的箱子箱子前是一个空位{map[x][y-1]=6;map[x][y-2]=5;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;}elseif(map[x][y-2]==0||map[x][y-2]==3||map[x][y-2]==5)//人前是已在空位是的箱子箱子前是墙箱子已在空位上的箱子{printf(\a);}elseif(map[x][y-2]==1)//人前是已在空位上的箱子箱子前是路{map[x][y-1]=6;map[x][y-2]=3;if(map[x][y]==4)map[x][y]=1;elsemap[x][y]=2;};};};break;}map1(map);return(map[9][10]);}intmap1(inta[9][10]){inti,j;staticintcount=0;system(cls);printf(\n\n\t\t\t欢迎选玩*【推箱子游戏】O(∩_∩)O~~~\n\n\t\t\t\t\t游戏规则：\n\t\t□:代表墙×：代表路○：代表空位\n\t\t●：代表箱子♀：代表人※：代表箱子已在空位上\n\t\t\t\t\t8:向上移动\n\t\t\t\t\t2:向下移动\n\t\t\t\t\t4:向左移动\n\t\t\t\t\t6:向右移动\n\t\t\t\t\t);for(i=0;i9;i++){printf(\n\t\t\t\t);for(j=0;j10;j++){switch(a[i][j]){case0:printf(□);break;//□代表墙case1:printf(×);break;//×代表路case2:printf(○);break;//○代表空位case3:printf(●);break;//●代表箱子c