Skip to content

1095: 推箱子

题目

题目描述

推箱子是一款经典的小游戏。游戏要求玩家将若干个箱子推到指定的位置,并以箱子移动次数最少作为目标。 现在,我们只需要考虑一个简化的版本——只有一个箱子。对于一张给定的地图,你需要判断是否可以将箱子推到目标位置,如果可以,你还需要求出箱子最少的移动次数。

输入格式

第一行有两个用单个空格分隔的正整数n,m(n,m<=100),表示输入一张n*m的地图。 接下来n行,每行m个字母,字母分别是S, M, P, K, w,意义如下: S – 表示地图中的墙 M – 表示玩家的初始位置 P – 表示箱子的初始位置 K- 表示箱子的目标位置 w – 表示地图中的空格 M, P 和 K 在文件中只出现一次

输出格式

如果箱子不能移动到目的位置,则输出NO。 如果箱子能移动到目的位置,则输出最小的移动次数。

样例输入

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

样例输出

7

数据范围

对于10%的数据: n=1或m=1

另10%的数据: n=5,m=100或 n=100,m=5

对于30%的数据: n,m<=50

对于100%的数据: n,m<=100

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!