题目描述

有一个 $n$ 行 $m$ 列的网格。行从上到下编号为 $1,2,\ldots,n$，列从左到右编号为 $1,2,\ldots,m$。网格中包含起点 S、终点 T、障碍 #、顺时针校准器 C、镜像校准器 M 和普通空地 .。

机器人有一份校准记录，初始为空。每当机器人停在校准器上，就将该校准器对应的字符追加到记录末尾。因此，校准记录中的字符按照停在校准器上的时间顺序排列。

每次行动前，分别从两个按钮的初始方向出发，依次读取整份校准记录，以确定按钮的实际方向：

• 按钮 A 的初始方向是上，按下后移动 $1$ 格；
• 按钮 B 的初始方向是右，按下后连续移动 $2$ 格；
• 读到 C 时，将当前方向顺时针旋转 $90$ 度；
• 读到 M 时，将当前方向关于竖直方向镜像，即上、下方向不变，左、右方向互换。

一次行动选择按钮 A 或按钮 B。机器人沿该按钮的实际方向移动规定的格数。只有移动经过的每一格都在网格内且不是障碍时，这次行动才合法。

一次合法行动结束后，只考虑机器人最终停下的格子：

• 如果停在 C 上，就在校准记录末尾加入一个 C；
• 如果停在 M 上，就在校准记录末尾加入一个 M；
• 停在其他格子上时，校准记录不变。

按钮 B 移动时经过但没有停下的格子不会改变校准记录；即使经过 T，也不算到达终点。机器人在 S 上开始时不会向校准记录加入字符。重复停在同一个校准器上时，每次都会加入相应字符。

每次合法行动的代价都是 $1$。请计算机器人最终停在 T 上所需的最少行动次数。如果无法到达，输出 $-1$。

输入格式

从文件 navigation.in 中读取数据。

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

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，描述网格。

输出格式

输出到文件 navigation.out 中。

输出一个整数，表示到达终点所需的最少行动次数；如果无法到达，输出 $-1$。

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

4

样例解释

样例 #1 中，可以依次按下 B、B、A、A：

1. 校准记录为空时，按钮 B 向右移动 $2$ 格，机器人停在 C 上，记录变为 C；
2. 记录 C 使按钮 B 的方向由右变下，机器人向下移动 $2$ 格并停在 M 上，记录变为 CM；
3. 对按钮 A 的初始方向“上”依次进行顺时针旋转和竖直镜像后，实际方向为左。连续按两次 A 即可到达 T。

在到达 T 前，上述每一步都是机器人的唯一的合法行动，因此最少需要 $4$ 次行动。

数据规模与约定

对于所有数据，保证：

• $1\le n,m\le 2000$；
• $2\le n\times m\le 300000$；
• 每行字符串长度均为 $m$，且只包含字符 .、#、C、M、S、T；
• S 和 T 各出现恰好一次，且位于不同格子；
• 除 # 外的所有格子都可以进入。

各子任务独立计分。每个子任务内的测试点捆绑评测，只有通过该子任务的全部测试点，才能获得对应分值。

下发文件

下载三组测试数据，非真实测试数据