推箱子问题的设计与实现

推箱子问题的设计与实现推箱子问题的设计与实现 实验报告 班级 计本四班 学号 2012020386 姓名 刘宝同 一 问题描述一 问题描述 码头仓库是划分为 n m 个格子的矩形阵列 有公共边的格子是相邻格子 当前仓库 中有的格子是空闲的 有的格子则已经堆放了沉重的货物 由于堆放的货物很重 单凭仓 库管理员的力量是无法移动的 仓库管理员有一项任务 要将一个小箱子推到指定的格子 上去 管理员可以在仓库中移动 但不能跨过已经堆放了货物的格子 管理员站在与箱子 相对的空闲格子上时 可以做一次推动 把箱子推到另一相邻的空闲格子 推箱时只能向 管理员的对面方向推 由于要推动的箱子很重 仓库管理员想尽量减少推箱子的次数 二 问题求解分析二 问题求解分析 对于给定的仓库布局 以及仓库管理员在仓库中的位置和箱子的开始位置和目标位置 设计一个解推箱子问题的分支限界法 计算出仓库管理员将箱子从开始位置推到目标位置 所需的最少推动次数 数据输入 由文件 input txt 提供输入数据 输入文件第 1 行有 2 个正整数 n 和 m 1 n m 100 表示仓库是 n m 个格子的矩形阵列 接下来有 n 行 每行有 m 个 字符 表示格子的状态 S 表示格子上放了不可移动的沉重货物 w 表示格子空闲 M 表示仓库管理员的初始位置 P 表示箱子的初始位置 K 表示箱子的目标位置 结果输出 将计算出的最少推动次数输出到文件 output txt 如果仓库管理员无法将箱子从 开始位置推到目标位置则输出 No solution 三 源程序关键代码三 源程序关键代码 include include include int map1 int a 9 10 char move char t int map 9 10 int i j x y system CLS 清屏 for i 0 i 9 i 查找当前人位置 for j 0 j 10 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 else map x y 2 else if 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 else map x y 2 else if map x 2 y 0 map x 2 y 3 map x 2 y 5 人前是箱子 箱子前面是 墙 箱子 已在空位上的箱子 printf a else if map x 2 y 1 人前是箱子 箱 子前面是路 map x 1 y 4 map x 2 y 3 if map x y 4 map x y 1 else map x y 2 else if map x 1 y 0 人前是墙 printf a else if map x 1 y 2 map x 1 y 6 if map x y 4 map x y 1 else map x y 2 else if 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 else map x y 2 else if map x 2 y 0 map x 2 y 3 map x 2 y 5 人前是已在空位是的箱子 箱子 前是墙 箱子 已在空位上的箱子 printf a else if map x 2 y 1 人前是已在空位上的箱 子 箱子前是路 map x 1 y 6 map x 2 y 3 if map x y 4 map x y 1 else map 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 else map x y 2 else if 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 else map x y 2 else if map x y 2 0 map x y 2 3 map x y 2 5 人前是 箱子 箱子前面是墙 箱子 已在空位上的 箱子 printf a else if map x y 2 1 人前是箱子 箱子前 面是路 map x y 1 4 map x y 2 3 if map x y 4 map x y 1 else map x y 2 else if map x y 1 0 人前是墙 printf a else if map x y 1 2 map x y 1 6 if map x y 4 map x y 1 else map x y 2 else if 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 else map x y 2 else if map x y 2 0 map x y 2 3 map x y 2 5 人前是已在空位是的箱子 箱子前是墙 箱子 已在空位上的箱子 printf a else if map x y 2 1 人前是已在空位上的箱 子 箱子前是路 map x y 1 6 map x y 2 3 if map x y 4 map x y 1 else map 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 else map x y 2 else if 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 else map x y 2 else if map x 2 y 0 map x 2 y 3 map x 2 y 5 人前是 箱子 箱子前面是墙 箱子 已在空位上的 箱子 printf a else if map x 2 y 1 人前是箱子 箱子前 面是路 map x 1 y 4 map x 2 y 3 if map x y 4 map x y 1 else map x y 2 else if map x 1 y 0 人前是墙 printf a else if map x 1 y 2 map x 1 y 6 if map x y 4 map x y 1 else map x y 2 else if 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 else map x y 2 else if map x 2 y 0 map x 2 y 3 map x 2 y 5 人前是已在空位是的箱子 箱子前是墙 箱子 已在空位上的箱子 printf a else if map x 2 y 1 人前是已在空位上的箱 子 箱子前是路 map x 1 y 6 map x 2 y 3 if map x y 4 map x y 1 else map 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 else map x y 2 else if 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 else map x y 2 else if map x y 2 0 map x y 2 3 map x y 2 5 人前是 箱子 箱子前面是墙 箱子 已在空位上的 箱子 printf a else if map x y 2 1 人前是箱子 箱子前 面是路 map x y 1 4 map x y 2 3 if map x y 4 map x y 1 else map x y 2 else if map x y 1 0 人前是墙 printf a else if map x y 1 2 map x y 1 6 if map x y 4 map x y 1 else map x y 2 else if 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 else map x y 2 else if map x y 2 0 map x y 2 3 map x y 2 5 人前是已在空位是的箱子 箱子前是墙 箱子 已在空位上的箱子 printf a else if map x y 2 1 人前是已在空位上的箱 子 箱子前是路 map x y 1 6 map x y 2 3 if map x y 4 map x y 1 else map x y 2 break map1 map return map 9 10 int map1 int a 9 10 int i j static int count 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 t 8 向上 移动 n t t t t t 2 向下移动 n t t t t t 4 向左 移动 n t t t t t 6 向右移动 n t t t t t for i 0 i 9 i printf n t t t t for j 0 j 10 j switch a i j case 0 printf break 代表墙 case 1 printf break 代表路 case 2 printf break 代表空位 case 3 printf break 代表箱子 case 4 printf break 代表人 case 5 printf break 代表箱子 已在空位上 case 6 printf break printf n t t t t 步数 d count printf n t t t t return a 9 10 int main char c int map 9 10 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 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 四 总结四 总结 通过对推