시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB1931229967.808%

문제

$N\times M$ 격자 위의 한 칸에 게가 살고 있다. 여기에는 노래가 없기 때문에, 게는 가장 가까운 바다로 가야 한다. 현재 격자의 각 칸은 게, 수돗물, 바다 중 정확히 하나가 놓여 있거나 비어 있다.

게는 격자의 축과 평행한 어떤 방향을 바라보고 있고, 게걸음으로 이동하거나 몸을 돌려 바라보는 방향을 바꿀 수 있다. 게걸음으로는 자신이 바라보는 방향에 수직한 방향으로 한 칸 이동할 수 있고, 이동하는 데 1의 시간이 걸린다. 몸을 한 번 돌리면 동일한 칸 위에서 자신이 원래 바라보던 방향에서 반시계방향으로 90도 돌아간 방향을 바라보게 되며, $T$의 시간이 걸린다.

게는 바다 칸이나 빈 칸, 자신이 원래 있던 칸을 자유롭게 돌아다닐 수 있지만, 수돗물 칸에서는 스스로 이동할 수 없다. 대신 게가 수돗물 칸에 들어가는 순간, 추가 시간 없이 아래 과정이 즉시 일어난다.

  1. 게의 몸이 반시계방향으로 90도 회전한다.
  2. 회전 직후 그 바라보는 방향으로 한 칸 이동한다.

만약 이동한 칸도 수돗물 칸이라면, 수돗물이 아닌 칸에 도착하거나 격자 밖으로 나가기 전까지 위 과정을 추가 시간 없이 계속 반복한다.

성현이는 당장이라도 끊어질 듯한 게가 자신의 칸에서 바다까지 격자를 한 번도 벗어나지 않고 이동할 수 있는지 알고 싶어한다. 바다까지 가는데 걸리는 최단 시간을 구하여라.

입력

첫째 줄에는 격자의 크기를 나타내는 정수 $N,M$과, 게가 몸을 돌리는 데 드는 시간을 나타내는 정수 $T$가 공백을 사이에 두고 주어진다. 이후 $N$줄에 걸쳐 격자의 상태가 주어진다. 이중 $i$번째 줄에는 격자의 $i$행이 주어지며, 각 문자가 의미하는 바는 아래와 같다.

  • .: 빈 칸
  • T: 수돗물
  • S: 바다 칸으로, 전체 격자에 최소 한 칸 이상 존재한다.
  • 0-3: 게가 존재하는 칸으로, 게가 바라보고 있는 방향을 의미한다. 0일 경우 위쪽, 1일 경우 왼쪽, 2일 경우 아래쪽, 3일 경우 오른쪽을 바라보고 있다. 게가 존재하는 칸은 격자에 정확히 한 칸 뿐이다.

출력

만약 게가 격자를 벗어나지 않고 바다에 도착할 수 없다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 바다에 도착하기까지 걸리는 최단 시간을 출력한다.

제한

  • 주어지는 모든 수는 정수이다.
  • $1\le N,M\le 500$
  • $1\le T\le 10^{4}$

예제 입력 1

4 5 3
T....
1T..S
TT...
.S..T

예제 출력 1

2

예제 입력 2

2 12 4
T.....3TTTS.
...T.T...T.T

예제 출력 2

11

예제 입력 3

2 4 1
0TTT
TTTS

예제 출력 3

-1

출처

Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup 4 : Grand Final B번