로봇의 이동

면접 대비

시간 제한1초메모리 제한128 MB

요약

N/S/E/W 화살표로 채워진 격자에 위쪽 열에서 들어온 로봇의 이동을 시뮬레이션하여, 격자를 벗어나기까지의 걸음 수 또는 순환이 시작되기까지의 걸음 수와 순환 길이를 구한다.

문제

로봇은 격자 위에 놓인 이동 명령을 따라 움직인다. 격자의 각 칸에는 다음에 어느 방향으로 이동할지를 알려 주는 명령이 하나씩 적혀 있다.

로봇은 격자의 북쪽(맨 위) 경계에서 주어진 열로 진입하여, 자신이 도착한 칸의 명령을 즉시 읽고 그 방향으로 한 칸 이동한다. 그리고 새로 도착한 칸의 명령을 다시 따르는 과정을 반복한다.

결국 다음 두 가지 중 정확히 하나가 반드시 일어난다.

각 격자에 대해, 로봇이 격자를 빠져나가기까지 몇 걸음을 이동하는지, 또는 루프에 빠지기까지 몇 걸음을 이동한 뒤 몇 걸음짜리 루프를 도는지를 구하는 프로그램을 작성하라.

입력은 하나 이상의 격자로 이루어진다. 각 격자는 다음 형식으로 주어진다.

첫 줄에는 공백으로 구분된 세 정수가 주어진다. 격자의 행 수 $R$ , 열 수 $C$ , 그리고 로봇이 북쪽에서 진입하는 열의 번호이다. 열은 왼쪽부터 1번으로 매긴다.

이어지는 $R$ 개의 줄이 격자의 각 행을 나타낸다. 각 줄은 정확히 $C$ 개의 문자로 이루어지며, 각 문자는 N, S, E, W 중 하나이고 공백은 없다.

모든 격자는 $1 \le R, C \le 10$ 을 만족한다. 입력의 끝은 0 0 0으로 이루어진 줄로 표시되며, 이 줄은 처리하지 않는다.

각 격자마다 정확히 한 줄을 출력한다.

로봇이 격자를 빠져나가는 경우:

X step(s) to exit

여기서 X는 로봇이 경계를 벗어나기 전까지 따른 명령의 수이다.
로봇이 루프에 빠지는 경우:

Y step(s) before a loop of Z step(s)

여기서 Y는 루프가 시작되기 전까지 따른 명령의 수이고, Z는 루프 한 바퀴에 포함된 명령의 수이다.

step이라는 단어 뒤에는 앞의 수가 1이든 아니든 항상 (s)가 곧바로 붙는다.

예제 1

입력

3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0 0

예상 출력

10 step(s) to exit
3 step(s) before a loop of 8 step(s)