该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

相位迷宫 (phase)

题目描述

第三层遗迹是一座 $N \times M$ 的能量迷宫。迷宫由空地（.）、不可穿透的墙壁（#）、起点（S）和终点（E）组成。

探险员身穿一套“星渊相位服”。这套服装共有 3 种相位状态（标记为 0, 1, 2）。初始处于起点时，相位服装状态默认为 0。

在迷宫中移动，必须遵循以下规则：

1. 移动：探险员可以花费 1 个单位时间，向上下左右相邻的格子移动一步。
2. 相位屏障：迷宫中存在三种特殊的相位门，分别用 A, B, C 表示。
   • A 类门：只有处于相位 1 的状态下才能走上去。
   • B 类门：只有处于相位 2 的状态下才能走上去。
   • C 类门：只有处于相位 0 的状态下才能走上去。
   • （注意：起点、终点和普通空地不需要特定相位即可走上）
3. 相位切换：探险员可以随时选择原地驻留 1 个单位时间，将服装的相位顺移切换到下一个状态（即 $0 \to 1$，$1 \to 2$，$2 \to 0$）。

已知起点必为 S，终点必为 E，请计算探险员从起点到达终点所需要的最短时间。如果无论如何都无法到达，输出 -1。

输入格式

第一行包含两个整数 $N, M$，表示迷宫的行数和列数。 接下来 $N$ 行，每行包含一个长度为 $M$ 的字符串，表示迷宫的地形。

输出格式

输出一个整数，表示最短时间。如果无法到达，输出 -1。

样例 #1

样例输入 #1

4 5
S.A..
###.#
C.B..
E####

样例输出 #1

12

样例解释 #1

1. 从 S 向右移动到 . （时间 1，相位 0）
2. 原地切换相位：0 -> 1 （时间 2，相位 1）
3. 向右移动穿过 A 门 （时间 3，相位 1）
4. 向下移动到 . （时间 4，相位 1）
5. 向下移动到 . （时间 5，相位 1）
6. 原地切换相位：1 -> 2 （时间 6，相位 2）
7. 向左移动穿过 B 门 （时间 7，相位 2）
8. 向左移动到 . （时间 8，相位 2）
9. 向下移动到 E （时间 9，相位 2）

数据范围

• 对于 $30\%$ 的数据，$N, M \le 50$，没有 A, B, C 相位门。
• 对于 $100\%$ 的数据，$1 \le N, M \le 1000$。