P5564. 迷宫最短救援

场次：2026年9月23日-非AI方向 · 来源：CodeFun2000 P5564

题目描述

穿越这片迷宫、把受困公主救出来，是王子此刻要办的事。毒雾正往四处散开，因此他得用尽量少的时间赶到公主身边。挡路的不只有墙，还有守在若干区域上的怪物。

题目内容

地图已经给出。王子从出发点动身，要算出抵达公主所在格的最少移动次数。

移动规则

• 每次只许朝上、左、下、右迈一格，斜向跨步不算合法
• 跑出地图边界的格子，一律按墙处理
• 墙所在的格子，王子踏不上去

怪物规则

• 怪物上、下、左、右紧挨的那一格，没拿到宝剑时都不能踏入
• 地图上会出现宝剑，王子能够把它捡起来
• 宝剑一旦到手，王子就具备击杀怪物的能力
• 宝剑到手之后，怪物上、下、左、右紧挨的格子也可以进入
• 宝剑到手之后，王子还能踏进怪物所在格，并且只击倒脚下这一只（其余怪物仍留在原地）
• 宝剑若正好放在怪物紧挨的格子上，王子仍可进入该格并把剑捡走
• 出发时若王子本人就站在怪物紧挨的格子上，这并不妨碍他迈出下一步（下一步应当离开危险格）

策略选择

王子得在两条路线里挑更省步数的一条：

• 先把宝剑拿到手再去击倒怪物，步数会不会更少
• 或者干脆不靠近怪物、从旁边绕，步数会不会更少

输入格式

数据来自标准输入。 第一行给出两个整数 $h$ 和 $w$，分别是地图的行数与列数（$1 \le h,w \le 100$），$h$ 与 $w$ 用空格隔开。 随后是 $h$ 行，每一行有 $w$ 个字符，用来描绘整张地图：

• $.$ 代表可以落脚的空地
• # 代表不能落脚的墙
• $S$ 代表王子出发的格子
• $P$ 代表公主所在的格子
• $M$ 代表一只怪物
• $W$ 代表一把宝剑

输入保证出发格 $S$ 与公主格 $P$ 都恰好出现一次。

输出格式

答案写到标准输出。只写出一个整数，即王子走到公主处所需的最少步数。 公主处不可达时，结果记成 $-1$。

示例

示例 1

输入：

3 3
S.M
...
.MP

输出：

-1

说明：

公主在右下角，左边紧挨着一只怪物，地图里又没有宝剑。没剑时那一格进不去，所以无解。

示例 2

输入：

3 5
S.#.P
..#..
W.M..

输出：

8

说明：

行列都从 $0$ 计。一条最短路线是 $(0,0)\rightarrow(1,0)\rightarrow(2,0)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(2,4)\rightarrow(1,4)\rightarrow(0,4)$，共 $8$ 步。$(2,0)$ 处捡到宝剑后才能穿过怪物及其左右两侧。列下标 $2$ 的前两行是墙，不拿剑就无法从左侧走到右侧的公主。

示例 3

输入：

1 5
S...P

输出：

4

说明：

这一行没有墙也没有怪物。王子从最左格一直向右，走到最右的公主处，步数是 $4$。