보물찾기

면접 대비

시간 제한2초메모리 제한512 MB

요약

격자의 각 칸에 적힌 방향을 따라 왼쪽 위에서 출발해 보물까지의 이동 횟수를 세고, 격자를 벗어나면 Out, 순환하면 Lost를 출력한다.

난이도: 보통10점 중 4점
유형: 시뮬레이션, 그래프, 구현, 행렬
정답자: 아직 제출이 없습니다

문제

질은 플레이어가 보물을 찾아가는 스마트폰 게임을 만들었다. 앱은 GPS로 플레이어의 위치를 파악하고, 그 위치에서 보물로 가는 경로의 다음 방향을 알려 준다. 플레이어가 보물이 놓인 위치에 도착하면 앱이 (가상의) 보물을 준다.

플레이어가 보물을 찾기까지 몇 번 이동하는지 구하라.

입력

첫째 줄에 두 정수 $R$ 과 $C$ 가 주어진다 ( $1 \le R \le 200$ , $1 \le C \le 200$ ). 각각 게임판의 행 개수와 열 개수다.

다음 $R$ 개 줄에는 게임판이 주어진다. 각 줄은 정확히 $C$ 개의 문자로 이루어지고, 문자 하나가 그 칸에서 할 행동을 정한다. 문자는 다섯 가지다. N은 이전 행으로, S는 다음 행으로, W는 이전 열로, E는 다음 열로 이동한다는 뜻이고, T는 보물이 놓인 위치다. 보물이 있는 칸은 정확히 하나다.

출력

플레이어는 첫째 행 첫째 열에서 시작해, 서 있는 칸에 적힌 방향을 따라 이동한다.

방향을 따라가다 보물에 도착하면 이동 횟수를 한 줄에 출력한다. 방향을 따라가다 게임판 밖으로 나가면 Out을 한 줄에 출력한다. 게임판 안에 계속 머물지만 보물에 끝내 도착하지 못하면 Lost를 한 줄에 출력한다.

예제5

예제 1
입력
```
2 2
ES
TW
```
예상 출력
```
3
```
예제 2
입력
```
1 1
T
```
예상 출력
```
0
```
예제 3
입력
```
1 2
WT
```
예상 출력
```
Out
```
예제 4
입력
```
2 2
EW
TN
```
예상 출력
```
Lost
```
예제 5
입력
```
3 3
SET
SNW
ENW
```
예상 출력
```
6
```