Problem 1424 --算法实现题 6-14 推箱子问题

1424: 算法实现题 6-14 推箱子问题

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

码头仓库是划分为 n×m 个格子的矩形阵列。有公共边的格子是相邻格子。当前仓库中有的格子是空闲的；有的格子则已经堆放了沉重的货物。由于堆放的货物很重，单凭仓库管理员的力量是无法移动的。仓库管理员有一项任务，要将一个小箱子推到指定的格子上去。
管理员可以在仓库中移动，但不能跨过已经堆放了货物的格子。管理员站在与箱子相对的空闲格子上时，可以做一次推动，把箱子推到另一相邻的空闲格子。推箱时只能向管理员的对面方向推。由于要推动的箱子很重，仓库管理员想尽量减少推箱子的次数。
«算法设计：
对于给定的仓库布局，以及仓库管理员在仓库中的位置和箱子的开始位置和目标位置，设计一个解推箱子问题的分支限界法， 计算出仓库管理员将箱子从开始位置推到目标位置所需的最少推动次数。

Input

输入第 1 行有 2 个正整数 n 和 m（1<=n,m<=100） ，表示仓库是 n×m 个格子的矩形阵列。接下来有 n 行，每行有 m 个字符，表示格子的状态。
S 表示格子上放了不可移动的沉重货物；
w 表示格子空闲；
M 表示仓库管理员的初始位置；
P 表示箱子的初始位置；
K 表示箱子的目标位置。

Output

将计算出的最少推动次数输出。如果仓库管理员无法将箱子从开始位
置推到目标位置则输出“No solution！” 。

Sample Input复制

10 12
SSSSSSSSSSSS
SwwwwwwwSSSS
SwSSSSwwSSSS
SwSSSSwwSKSS
SwSSSSwwSwSS
SwwwwwPwwwww
SSSSSSSwSwSw
SSSSSSMwSwww
SSSSSSSSSSSS
SSSSSSSSSSSS

Sample Output复制

7

推荐代码 查看1424 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战 大喵-sama 900302 2022-10-11 16:20:03

赛题来源/所属竞赛 分支限界 算法导论(第三版)中文完整高清版

竞赛编号 竞赛名称 竞赛时间 访问比赛