Treasure Hunt

Interview

Time limit2sMemory limit512 MB

Summary

Follow a grid of arrows from the top-left cell and report the number of steps to the treasure, Out if you leave the grid, or Lost if you loop forever.

Level: Medium4 of 10
Topics: Simulation, Graph, Implementation, Matrix
Solved: No attempts yet

Problem

Jill wrote a smartphone game that leads players to a treasure. The app reads the player's location from GPS, then tells the player which direction to go next on the route to the treasure. When the player reaches the location of the treasure, the app hands over a (virtual) treasure.

Work out how many moves the player needs to find the treasure.

Input

The first line contains two integers $R$ and $C$ ( $1 \le R \le 200$ , $1 \le C \le 200$ ), the number of rows and the number of columns of the playing area.

The next $R$ lines describe the playing area. Each line contains exactly $C$ letters, and each letter fixes the action taken in that location. There are five possible letters: N means a move to the previous row, S means a move to the next row, W means a move to the previous column, E means a move to the next column, and T marks the location of the treasure. Exactly one location contains the treasure.

Output

The player starts at the location in the first column of the first row and follows the direction written in each location.

If the directions bring the player to the treasure, print one line with the number of moves required to reach it. If the directions take the player out of the playing area, print one line containing Out. If the directions keep the player inside the playing area but never reach the treasure, print one line containing Lost.

Examples5

Example 1
Input
```
2 2
ES
TW
```
Expected output
```
3
```
Example 2
Input
```
1 1
T
```
Expected output
```
0
```
Example 3
Input
```
1 2
WT
```
Expected output
```
Out
```
Example 4
Input
```
2 2
EW
TN
```
Expected output
```
Lost
```
Example 5
Input
```
3 3
SET
SNW
ENW
```
Expected output
```
6
```