| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 193 | 122 | 99 | 67.808% |
$N\times M$ 격자 위의 한 칸에 게가 살고 있다. 여기에는 노래가 없기 때문에, 게는 가장 가까운 바다로 가야 한다. 현재 격자의 각 칸은 게, 수돗물, 바다 중 정확히 하나가 놓여 있거나 비어 있다.
게는 격자의 축과 평행한 어떤 방향을 바라보고 있고, 게걸음으로 이동하거나 몸을 돌려 바라보는 방향을 바꿀 수 있다. 게걸음으로는 자신이 바라보는 방향에 수직한 방향으로 한 칸 이동할 수 있고, 이동하는 데 1의 시간이 걸린다. 몸을 한 번 돌리면 동일한 칸 위에서 자신이 원래 바라보던 방향에서 반시계방향으로 90도 돌아간 방향을 바라보게 되며, $T$의 시간이 걸린다.
게는 바다 칸이나 빈 칸, 자신이 원래 있던 칸을 자유롭게 돌아다닐 수 있지만, 수돗물 칸에서는 스스로 이동할 수 없다. 대신 게가 수돗물 칸에 들어가는 순간, 추가 시간 없이 아래 과정이 즉시 일어난다.
만약 이동한 칸도 수돗물 칸이라면, 수돗물이 아닌 칸에 도착하거나 격자 밖으로 나가기 전까지 위 과정을 추가 시간 없이 계속 반복한다.
성현이는 당장이라도 끊어질 듯한 게가 자신의 칸에서 바다까지 격자를 한 번도 벗어나지 않고 이동할 수 있는지 알고 싶어한다. 바다까지 가는데 걸리는 최단 시간을 구하여라.
첫째 줄에는 격자의 크기를 나타내는 정수 $N,M$과, 게가 몸을 돌리는 데 드는 시간을 나타내는 정수 $T$가 공백을 사이에 두고 주어진다. 이후 $N$줄에 걸쳐 격자의 상태가 주어진다. 이중 $i$번째 줄에는 격자의 $i$행이 주어지며, 각 문자가 의미하는 바는 아래와 같다.
.: 빈 칸T: 수돗물S: 바다 칸으로, 전체 격자에 최소 한 칸 이상 존재한다.0-3: 게가 존재하는 칸으로, 게가 바라보고 있는 방향을 의미한다. 0일 경우 위쪽, 1일 경우 왼쪽, 2일 경우 아래쪽, 3일 경우 오른쪽을 바라보고 있다. 게가 존재하는 칸은 격자에 정확히 한 칸 뿐이다.만약 게가 격자를 벗어나지 않고 바다에 도착할 수 없다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 바다에 도착하기까지 걸리는 최단 시간을 출력한다.
4 5 3 T.... 1T..S TT... .S..T
2
2 12 4 T.....3TTTS. ...T.T...T.T
11
2 4 1 0TTT TTTS
-1
Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup 4 : Grand Final B번