魔法迷宫（maze）

题目描述

$\text{DAMON THRONE}$ 的训练系统生成了一个 $n$ 行 $m$ 列的魔法迷宫。

迷宫中的每个格子可能是：

• $\texttt{.}$：空地，可以经过；
• $\texttt{\#}$：墙壁，不能经过；
• $\texttt{S}$：起点；
• $\texttt{T}$：终点；
• $\texttt{M}$：魔法点。

小 D 从起点 $\texttt{S}$ 出发，每一步可以向上、下、左、右相邻的格子移动一格，不能走出迷宫，也不能走到墙壁上。

普通移动每次花费 $1$ 点体力。

当小 D 第一次到达任意一个魔法点 $\texttt{M}$ 时，会获得一次魔法冲刺机会。之后他可以在某一步移动时使用这次机会，使这一步移动的花费变为 $0$。

魔法冲刺机会最多只能获得一次，也最多只能使用一次。

请你求出小 D 从 $\texttt{S}$ 到 $\texttt{T}$ 的最小体力花费。

如果无法到达终点，输出 $-1$。

输入格式

第一行包含两个整数 $n,m$，表示迷宫的行数和列数。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示迷宫。

保证迷宫中恰好有一个 $\texttt{S}$ 和一个 $\texttt{T}$。

输出格式

输出一行一个整数。

如果可以从起点到达终点，输出最小体力花费；否则输出 $-1$。

输入输出样例 #1

输入 #1

3 5
S.M..
###.#
...T.

输出 #1

4

样例解释 #1

一种最优路线为：

S -> (1,2) -> M -> (1,4) -> (2,4) -> T

从 $\texttt{S}$ 到达魔法点 $\texttt{M}$ 需要 $2$ 步，花费 $2$ 点体力。

到达 $\texttt{M}$ 后，获得一次魔法冲刺机会。之后可以选择从 $\texttt{M}$ 移动到 $(1,4)$ 时使用魔法冲刺，使这一步花费为 $0$。

然后继续从 $(1,4)$ 走到 $(2,4)$，再走到 $\texttt{T}$，还需要花费 $2$ 点体力。

所以最小体力花费为：

输入输出样例 #2

输入 #2

3 4
S###
####
###T

输出 #2

-1

数据范围与约定

对于所有测试数据，保证：

迷宫中只包含字符 \texttt{.,#,S,T,M}，且恰好有一个 $\texttt{S}$ 和一个 $\text{T}$。

特殊性质 $\text{A}$：保证迷宫中没有魔法点 $\texttt{M}$。

特殊性质 $\text{B}$：保证迷宫中没有墙壁 $\texttt{\#}$。

特殊性质 $\text{C}$：保证最多只有一个魔法点 $\texttt{M}$。