마법의 미로

시간 제한3초메모리 제한1024 MB

요약

두 쌍둥이가 매초 같은 방향으로 동시에 움직여 두 출구에 함께 도달하는 최소 시간을 구합니다.

난이도: 보통10점 중 5점
유형: BFS, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

미라와 쌍둥이 남동생 리엄은 사악한 마녀에게 붙잡혀 미로에 갇혔다. 마녀는 쌍둥이를 미로의 서로 다른 위치에 두었다. 마녀가 애완 드래곤을 풀어놓기 전에 둘은 미로를 빠져나와야 한다. 쌍둥이는 가장 짧은 시간에 탈출할 수 있도록 도와 달라고 부탁했다.

마녀는 쌍둥이에게 저주도 걸었다. 쌍둥이는 동서남북 중 어느 방향으로든 이동을 시도할 수 있지만, 같은 시각에 반드시 같은 방향으로 이동을 시도해야 한다. 예를 들어 미라가 북쪽으로 이동을 시도하면 리엄도 같은 시각에 북쪽으로 이동을 시도해야 한다. 이동을 시도할 때마다 성공 여부와 관계없이 1초가 걸린다.

미로는 직사각형 격자이며, 각 칸은 다음 중 하나이다.

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를 제어한다. 같은 표지의 스위치는 최대 하나이지만, 한 스위치가 장애물 여러 개를 제어할 수 있다.

쌍둥이는 같은 칸에 동시에 있을 수 없다. 쌍둥이 중 한 명이 고정 장애물이나 올라가 있는 장애물로 이동을 시도하면 그 자리에 머문다. 미로 밖으로 나간 쌍둥이는 영원히 사라진다. 시작 칸과 출구 칸은 자유롭게 드나들 수 있다.

스위치는 쌍둥이가 그 위로 이동하면 작동한다. 작동하면 제어하는 장애물 중 내려가 있던 것은 올라가고, 올라가 있던 것은 내려간다. 쌍둥이 한 명이 이미 스위치 위에 있는데 이동을 시도한 결과 그 자리에 머문다면 스위치는 작동하지 않는다.

한 쌍둥이가 올라가 있는 장애물로 이동을 시도하는 동시에 다른 쌍둥이가 그 장애물을 제어하는 스위치를 밟으면, 그 이동 동안에는 장애물이 여전히 올라가 있고 이동이 끝날 때에야 내려간다. 한 쌍둥이가 스위치 위로 이동하는 동시에 다른 쌍둥이가 대응하는 내려가 있는 장애물로 이동하거나 그 자리에 머무르면, 그 쌍둥이는 스위치 위로 이동할 수 없다.

입력

첫 줄에 미로의 행 수 $R$ 과 열 수 $C$ 가 주어진다. 단, $2 \leq R \leq 10$ , $2 \leq C \leq 10$ 이다. 이어서 $R$ 개의 줄에 각각 $C$ 개의 문자로 미로가 주어진다. 쌍둥이가 탈출할 수 있는 미로만 입력으로 주어진다.

출력

쌍둥이가 탈출하는 데 걸리는 최소 시간(초)을 출력한다.

예제3

예제 1
입력
```
6 4
...E
S***
#***
S***
...E
.***
```
예상 출력
```
6
```
예제 2
입력
```
5 2
cE
E.
..
3.
SS
```
예상 출력
```
4
```

예제 3

입력

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

예상 출력