| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 118 | 84 | 77 | 73.333% |
우연이는 수업 시간에 멍하니 있다가, 현실 세계에서 미로에 갇히면 어떻게 해야 확실하게 탈출할 수 있을지 문득 궁금해졌다.
수업이 끝난 후, 그는 그 방법을 인터넷에서 찾아보다가 좌수법이라는 기법을 알게 되었다. 깨달음을 얻은 우연이는 옆에 앉아 있던 보경이에게 "좌수법을 쓰면 미로를 무조건 탈출할 수 있다."라고 말했다. 하지만 보경이는 이미 그 방법을 알고 있었고, 직접 사용해 본 결과 좌수법보다 우수법이 더 낫다고 주장했다.
$N$개의 행과 $M$개의 열로 이루어진 격자 모양의 미로가 주어진다. 미로의 칸은 빈칸, 벽, 입구, 출구 중 하나의 상태를 갖는다. 입구에서의 시선은 가장 가까운 빈칸을 향한다.
좌수법과 우수법은 다음의 세 가지 행동을 조합하여 수행할 수 있다.
좌수법의 경우 아래 의사 코드를 따라 움직인다.
while 도착 지점에 도착하지 않음 : 좌회전한다 while 전진 할 수 없음 : 우회전한다 전진한다
우수법의 경우 아래 의사 코드를 따라 움직인다.
while 도착 지점에 도착하지 않음 : 우회전한다 while 전진 할 수 없음 : 좌회전한다 전진한다
보경이의 자신만만한 말투에 괜히 기분이 상한 우연이는 좌수법이 더 우수한 방법이라며 맞섰고, 결국 둘은 어떤 방법이 더 좋은지를 직접 프로그램으로 구현해 확인해 보기로 했다.
첫째 줄에 두 정수 $N,ドル $M$가 공백으로 구분되어 주어진다. $(3 \le N, M \le 1,000円)$
이어서 $N$개의 줄에 걸쳐 길이 $M$의 문자열이 주어진다. $i+1$번째 줄의 $j$번째 문자는 위에서 $i$번째 행과 왼쪽에서 $j$번째 열이 교차하는 칸의 상태를 나타낸다.
.은 빈칸, *은 벽, S는 입구, E는 출구를 의미한다.
두 지점 S와 E는 입력 전체에 각각 한 번씩 등장하고, 좌우상하 어떤 방향으로도 인접하지 않으며, 미로의 가장자리에 위치한다. 가장자리에 빈칸 .은 위치하지 않는다.
탈출이 가능한 경우만 주어진다.
좌수법을 사용할 경우 먼저 탈출이 가능하다면 LEFT IS BEST를, 우수법을 사용할 경우 먼저 탈출이 가능하다면 RIGHT IS BEST를 출력한다.
어느 방법을 써도 동일한 최단 시간에 탈출이 가능할 경우 SAME을 출력한다.
5 5 ***** *...* *...* S...* ***E*
RIGHT IS BEST
13 9 ********* S.......* *.***.*.* *.*.*.*.* *.*.*.*.* *.*.*.*.* *.*.*.*** *.*.*.*.* *.*.*.*.* *.*.*.*.* *.*.*.*.* *.*.....* *******E*
LEFT IS BEST
4 4 *E** *.** *..* **S*
SAME