魔法迷宫 - 問題

Mila 和她的双胞胎弟弟 Liam 被一个邪恶的女巫困住了。女巫将这对双胞胎放在迷宫中不同的位置，他们必须在女巫放出宠物龙之前找到逃出迷宫的路。双胞胎请求你帮助他们在最短的时间内逃离迷宫。

为了增加难度，女巫对双胞胎施了咒语。虽然双胞胎可以尝试向四个罗盘方向（北、南、东、西）中的任意一个移动，但他们必须在同一时间尝试向同一个方向移动。例如，如果 Mila 尝试向北走一步，Liam 也必须在同一时间尝试向北走。无论移动是否成功，双胞胎的每一次尝试移动都需要一秒钟来完成。

迷宫由一个矩形网格表示，每个位置可以是以下类型之一：

起点 (S)：双胞胎的起始位置。恰好有两个起始位置，每个双胞胎一个。
出口 (E)：如果双胞胎同时处于出口位置，他们就逃脱了。恰好有两个出口位置。
空地 (.)：双胞胎可以自由进出此位置。
固定障碍物 (#)：双胞胎不能移动到此位置。
无底洞 (*)：移动到洞里的双胞胎将永远迷失。
抬起的障碍物 (A, B, C, D)：这些障碍物可以通过踩在相应的开关上来降低。
降低的障碍物 (a, b, c, d)：这些位置被视为开放的，但可以通过踩在相应的开关上来抬起。
开关 (1, 2, 3, 4)：控制障碍物的开关。开关 1 控制标记为 A 和 a 的障碍物，开关 2 控制标记为 B 和 b 的障碍物，开关 3 控制标记为 C 和 c 的障碍物，开关 4 控制标记为 D 和 d 的障碍物。每种标签的开关最多只有一个，但每个开关可以控制多个障碍物。

双胞胎不能在同一时间处于同一位置。如果一个双胞胎尝试移动到固定障碍物或抬起的障碍物中，该双胞胎将保持原地不动。移动到迷宫边界之外的双胞胎将永远迷失。在旅途中，他们也被允许进入和离开起点和出口位置。

当双胞胎移动到开关上时，开关会被触发。当开关被触发时，相应的障碍物会被抬起（如果当前是降低的）或降低（如果当前是抬起的）。如果双胞胎已经在开关上并且在尝试移动后保持原地不动，则开关不会被触发。

如果一个双胞胎尝试移动到抬起的障碍物，同时另一个双胞胎踩在相应的开关上，该障碍物仍被视为抬起，并且仅在移动结束时降低。如果另一个双胞胎同时正在移动到或保持在相应的降低的障碍物上，则一个双胞胎不能移动到开关上。

输入的第一行包含两个整数 $2 \le R \le 10$ 和 $2 \le C \le 10$，分别指定迷宫的行数和列数。接下来的 $R$ 行每行包含 $C$ 个字符。所有可能的字符已在上面说明。双胞胎总是可以逃离迷宫。

输出双胞胎逃离所需的最少秒数。

6 4
...E
S***
#***
S***
...E
.***

5 2
cE
E.
..
3.
SS

3 10
..........
.SS....EE.
..........

QOJ.ac