JY 的头疼光环 (JY's Headache Aura)

题目背景

期末复习周到了，JY 决定去学校最大、最像迷宫的地下图书馆自习。 但是，JY 是一个极度偏科、一看到数学题就会头疼的同学。不幸的是，此时正值考研大军复习《高等数学》和《离散数学》的高峰期，图书馆的许多书桌上都放着厚厚的数学书。 对 JY 来说，这些数学书就像是核废料一样，会向四周散发出可怕的“头疼光环”。距离某本数学书越近，JY 感受到的“头疼指数”就越高；距离越远，他就越有安全感。

题目描述

图书馆可以看作是一个 $N \times M$ 的网格地图。 地图中的每个格子可能是以下几种情况之一：

• .：空地，可以自由通行。
• #：书架或墙壁等障碍物，无法通行。
• M：放着数学书的桌子（数学书辐射源），JY 不能走到这些格子上。
• S：JY 的当前位置（起点）。
• E：JY 想要到达的安全自习室（终点）。

我们定义某个空地格子的**“安全指数”为：该格子到离它最近的一个数学书 (M) 的曼哈顿距离**。 （注：网格中两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的曼哈顿距离为 $|x_1 - x_2| + |y_1 - y_2|$）。

JY 想从起点 S 走到终点 E（每次只能上下左右移动一步，不能穿过障碍物和数学书）。 在走过的这条路线上，必然会有一个格子离数学书最近（即安全指数最小，头疼指数最高）。JY 希望规划出一条完美的路线，使得这条路线上所有格子中最小的“安全指数”尽可能大（也就是离数学书最远）。

因为 JY 对于数学与关于数学的信竞题一窍不通，所以他请你帮忙计算出，所有可行路线中，最大的“最小安全指数”是多少？ 如果他无论如何都无法从 S 走到 E，请输出 -1。

输入格式

第一行包含两个整数 $N, M$，表示图书馆网格的行数和列数。 接下来 $N$ 行，每行包含一个长度为 $M$ 的字符串，代表图书馆的地图。 保证地图中恰好有一个 S，恰好有一个 E，并且至少有一个 M。

输出格式

输出一个整数，表示路线中最大的“最小安全指数”。如果无法到达，输出 -1。

输入输出样例

输入样例 #1

5 5
S...M
.....
....#
#...#
M...E

输出样例 #1

2

输入样例 #2

3 3
S..
###
..E

输出样例 #2

-1

说明/提示

【样例解释 1】

有两个数学书 M，分别在 $(0, 4)$ 和 $(4, 0)$。 最优路线之一是：(0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2) -> (3,2) -> (4,2) -> (4,3) -> (4,4)。 在这条路线中，距离数学书最近的格子是起点 $(0,0)$ 和终点 $(4,4)$ 以及中间的 $(2,2)$ 等，它们到最近的 M 的曼哈顿距离为 4（例如 (0,0) 到 (4,0) 距离为 4）。 但是等等，路线如果往右走，比如经过 $(0,1)$，它到 $(0,4)$ 的距离只有 3。 实际上，最优路径在中间穿插，所有经过的格子中，到最近的 M 的最小距离（安全指数）最大能保持在 $2$。

【样例解释 2】

被墙壁完全堵死，无法到达，输出 -1。

数据规模与约定

• 对于 $30\%$ 的数据，$1 \le N, M \le 50$。
• 对于 $100\%$ 的数据，$1 \le N, M \le 1000$。地图仅由 ., #, M, S, E 组成。