포탈들 Batch 컴파일 명령

미로에 케이크 하나가 놓여져 있고 여러분은 그것을 절실하게 먹고 싶습니다. 여러분은 미로의 지도를 가지고 있으며, 이 지도는 $R$행 $C$열의 직사각형 격자판 형태입니다. 각 격자는 아래 문자들 중 하나를 포함합니다.

• # : 벽을 나타냅니다.
• . : 통로를 나타냅니다. 통로에서는 자유롭게 이동할 수 있습니다.
• S : 여러분의 초기 위치를 나타냅니다.. 이 격자는 통로입니다.
• C : 케익이 들어 있는 격자를 나타냅니다. 이 격자는 통로입니다.

여러분은 통로에서만 자유롭게 걸어다닐 수 있으며 한 격자에서 다른 격자로 이동하려면 이 두 격자는 한 변을 공유해야 합니다. 게다가, 지도에 나타내어진 직사각형 영역은 벽 격자로 완전히 둘러싸여 있습니다.

케이크에 가능한 한 빨리 도달하기 위하여 여러분은 Aperture Science^TM에서부터 포탈건을 습득했습니다. 이 총은 다음과 같이 작동합니다. 이 총은 아무 시간에나 위, 왼쪽, 아래와 오른쪽으로 포탈을 발사할 수 있습니다. 포탈이 어떤 방향으로 발사되었다면, 이는 벽에 첫 번째로 닿을 때까지 계속 날아갈 것입니다. 벽에 닿는 순간, 포탈은 여러분과 마주보는 변 위에 장착될 것입니다.

어떤 순간에도 최대 2개의 포탈만이 존재할 수 있습니다. 만약 두 개의 포탈이 이미 미로에 장착되어 있을 때 포탈을 발사하고 싶다면 여러분은 이미 존재하는 포탈들 중 하나를 선택하여 제거한 뒤 포탈을 발사해야 합니다. (편집자 주: 제거하기 위해 해당 포탈과 같은 열 또는 행에 이동할 필요는 없습니다. 발사 즉시 알아서 제거된다고 생각하면 됩니다.) 존재하는 포탈로 발사하면 그것을 교체할 것입니다. (벽의 한 변에는 최대 한 개의 포탈이 장착될 수 있습니다)

미로에 두 개의 포탈이 장착된다면 여러분은 이를 이용해서 순간 이동을 할 수 있습니다. 여러분이 포탈 옆에 서 있다가, 그 안으로 걸어 들어가면 다른 포탈 앞의 통로 격자로 순간 이동하게 됩니다. 순간을 이동하는 데 걸리는 시간은 인접한 두 격자 사이를 이동하는 데 걸리는 시간과 같습니다.

여러분은 포탈을 발사하는 데 아무 시간도 걸리지 않고 두 격자 사이를 이동하거나 포탈들 사이를 이동하는 데 1초가 걸린다고 가정해도 좋습니다.

해야 할 일

미로의 지도와 여러분의 초기 위치, 그리고 케이크의 위치가 주어질 때, 여러분은 케이크에 도달하기 위해 필요한 최소 시간을 구해야 합니다.

입력 형식

첫 번째 줄에 지도의 행의 수 $R$과 열의 수 $C$가 주어집니다. 다음 $R$개 줄에는 지도가 주어집니다. 각 줄에는 $C$개의 문자가 주어지며 이 문자들은 #, ., S 또는 C 중 하나입니다. (의미는 위에 서술되어 있습니다.)

S와 C는 지도에서 각각 단 한 번 등장함이 보장됩니다.

출력 형식

첫 번째 줄에 출발 위치에서 케이크까지 도달하는 데 걸리는 최소 시간을 초 단위로 출력합니다. 입력은 도달 가능하도록 주어진다고 가정해도 좋습니다.

예제

참고

가장 빨리 도착할 수 있는 방법 중 하나는 아래와 같습니다:

1. 오른쪽으로 이동합니다.
2. 오른쪽으로 이동한 뒤, 포탈 하나를 위로 발사하고, 또다른 포탈을 아래로 발사합니다.
3. 아래에 발사된 포탈을 향해 이동합니다.
4. 오른쪽으로 한 칸 이동하여 케이크에 도달합니다.

채점 방식

서브태스크 1 (11점)

• $1 \le R \le 10$
• $1 \le C \le 10$

서브태스크 2 (20점)

• $1 \le R \le 50$
• $1 \le C \le 50$

서브태스크 3 (20점)

• $1 \le R \le 200$
• $1 \le C \le 200$
• 모든 통로에게는 적어도 한 개 이상의 인접한 (한 변을 공유하는) 벽 격자가 있습니다.

서브태스크 4 (19점)

• $1 \le R \le 200$
• $1 \le C \le 200$

서브태스크 5 (30점)

• $1 \le R \le 1,000$
• $1 \le C \le 1,000$

제약 조건

시간 제한: 1 초.

메모리 제한: 256 MB.