포털

미로 안에 케이크가 놓여 있고, 그 케이크를 꼭 먹고 싶다. 미로 지도는 $R$행 $C$열 격자이고, 각 칸에는 다음 문자 중 하나가 적혀 있다.

• #: 벽 블록
• .: 빈 칸
• S: 현재 위치인 빈 칸
• C: 케이크가 놓인 빈 칸

빈 칸 위로만 걸어 다닐 수 있고, 변을 맞대고 있는 두 빈 칸 사이로만 움직일 수 있다. 지도에 그려진 직사각형 영역의 바깥은 전부 벽 블록으로 둘러싸여 있다.

케이크에 더 빨리 닿으려고 포털 건을 하나 구했다. 포털 건은 이렇게 동작한다. 언제든지 위, 왼쪽, 아래, 오른쪽 네 방향 중 하나로 포털을 쏠 수 있다. 포털은 쏜 방향으로 날아가다가 처음 만나는 벽에서 멈추고, 그 벽 블록의 면 중 내 쪽을 향한 면에 포털이 생긴다.

포털은 같은 시각에 최대 두 개까지 존재한다. 이미 두 개가 놓인 상태에서 포털 건을 다시 쏘면, 둘 중 내가 고른 하나가 즉시 사라진다. 이미 포털이 있는 면에 포털을 쏘면 그 포털을 덮어쓴다. 벽 블록의 한 면에는 포털이 최대 하나만 있을 수 있고, 같은 벽 블록의 서로 다른 면에는 포털을 하나씩 놓을 수 있다.

포털 두 개가 미로에 놓이면 그것으로 순간이동을 할 수 있다. 두 포털 중 하나의 바로 옆 칸에 서 있을 때 그 포털 안으로 걸어 들어가면, 다른 포털 바로 옆의 빈 칸으로 나온다. 이때 걸리는 시간은 인접한 두 칸 사이를 움직이는 시간과 같다.

포털을 쏘는 데는 시간이 걸리지 않는다. 인접한 두 칸 사이를 움직이거나 포털로 순간이동하는 데는 각각 1의 시간이 걸린다. 한번 놓인 포털은 사라지기 전까지 그 자리에 그대로 남으므로, 포털을 쏜 뒤 다른 곳으로 걸어가서 그 포털을 쓸 수 있다.

미로 지도와 시작 위치, 케이크 위치가 주어진다. 케이크에 도달하는 데 필요한 최소 시간을 구하라.

첫 줄에 지도의 행 수 $R$과 열 수 $C$가 주어진다 ($1 \le R, C \le 200$). 다음 $R$개의 줄에 지도가 주어지고, 각 줄은 #, ., S, C 중 하나인 문자 $C$개로 이루어진다.

S와 C는 지도에 각각 정확히 한 번씩 나타난다.

시작 위치에서 케이크까지 가는 데 필요한 최소 시간을 정수 하나로 출력한다.

시작 위치에서 케이크까지 갈 수 있음이 보장된다.

첫 번째 예제에서 가장 빠른 이동 방법 중 하나는 다음과 같다. 오른쪽으로 한 칸, 다시 오른쪽으로 한 칸 움직인 뒤, 위쪽으로 포털 하나와 아래쪽으로 포털 하나를 쏜다. 아래쪽 포털로 걸어 들어가고, 마지막으로 오른쪽으로 한 칸 움직이면 케이크에 닿는다.