算法实现题 推箱子问题

´问题描述： 码头仓库是划分为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！” 。 输入文件示例 输出文件示例 input.txt output.txt