창고를 순찰하는 로봇이 \(R \times C\) 크기의 격자 위에서 움직인다. 각 칸은 다음 중 하나이다.

• S : 로봇의 시작 위치 (정확히 하나)
• C : 충전소 (정확히 하나)
• . : 자유롭게 지나갈 수 있는 빈 칸
• # : 장애물 (들어갈 수 없음)

로봇은 한 번에 상하좌우로 인접한 칸으로 한 칸씩 이동할 수 있으며, 장애물 칸으로는 이동할 수 없다. 한 칸 이동할 때마다 에너지를 \(1\) 만큼 소모한다.

배터리가 떨어지기 전에 충전소에 도착하려면 로봇이 소모하는 에너지를 최소로 해야 한다. 시작 위치 S 에서 충전소 C 까지 도달하는 데 필요한 최소 이동 횟수를 구하여라. 만약 충전소에 도달할 수 없다면 \(-1\) 을 출력한다.

\(1 \le R, C \le 1{,}000\)

격자에는 S 와 C 가 각각 정확히 하나씩 존재한다.

첫째 줄에 두 정수 \(R\), \(C\) (\(1 \le R, C \le 1{,}000\)) 가 공백으로 구분되어 주어진다.

다음 \(R\) 개의 줄에는 각각 길이 \(C\) 의 문자열이 주어지며, 격자의 한 행을 나타낸다. 각 문자는 S, C, ., # 중 하나이다. S 와 C 는 격자 전체에 각각 정확히 한 번씩 등장한다.

S 에서 C 까지 이동하는 데 필요한 최소 이동 횟수를 한 줄에 출력한다. 도달할 수 없으면 \(-1\) 을 출력한다.

riseoj 작성

출처 Original