推箱子问题的算法实现题目

简介：
本项目探讨了“推箱子”游戏中的经典谜题解决策略，通过设计和实现多种算法（如A*、遗传算法）来寻找最优解或可行解路径。 问题描述：码头仓库是一个由n×m个格子构成的矩形阵列。有公共边界的格子被视为相邻。当前的状态是部分格子为空闲状态；其余则堆放了无法移动的沉重货物。由于箱子非常重，管理员只能在空闲且不被其他物品阻挡的格子里行走，并仅能将箱子推到与自己直接相邻并且也是空闲的目标位置上。每次推动只能朝向与其相对的方向进行，并且要尽量减少总的推动次数。 编程任务：给定仓库布局、管理员的位置以及箱子从初始位置到达目标位置的信息，设计一种分支限界法以计算出最少的推动次数。 数据输入：通过名为input.txt的文件提供输入信息。该文件的第一行包含两个正整数n和m（1<=n,m<=100），表示仓库由一个n×m格子构成。接下来有n行，每行包括m个字符来描述每个格子的状态。“S”代表堆放了沉重货物；“w”表示空闲状态；M标识管理员的初始位置；P表明箱子的位置起点；而“K”则指出了箱子的目标终点。 结果输出：将计算出所需的最少推动次数写入文件output.txt。如果无法找到从起始点到目标点的有效路径，则在该文件中输出No solution！ 示例输入与输出： 假设input.txt的内容如下： ``` 3 4 S w S K w M P w S w S w ``` 对于上述的布局，假如经过计算得出最少推动次数为2次，那么output.txt应包含以下内容： ``` 2 ```