Description

A city street toll system was recently established. A car must pay $1$ for each left turn and $5$ for each right turn. A U-turn is allowed only when going straight, turning left, and turning right are all impossible; each U-turn costs $10$.

Given a city map, find the path from the start to the finish with the minimum cost. Fortunately, all roads run due north, due south, due west, or due east.

Input Format

The input format is as follows:

1. The first line contains two integers, the map height $h$ and width $w$.
2. Then follow $h$ lines, each with $w$ characters, each being one of the following:

• . denotes an obstacle.
• # denotes a road.
• E denotes the start, with the car facing east.
• W denotes the start, with the car facing west.
• N denotes the start, with the car facing north.
• S denotes the start, with the car facing south.
• F denotes the finish.

Output Format

Output a single integer: the cost of the cheapest path.

8 11
...........
....#####..
....#...#..
....#...#..
.#E######..
....#......
.##F#......
...........

8

17 21
.....................
.#######.............
.#.....#.......#.....
.###...#.......#.....
...#...#.......#.....
.###...#.......#.....
.#.....#.......#.....
.############F#####..
.......#..........#..
.......#..........#..
...#...#...#####..#..
...#...#...#.#.#..#..
..#S########.#.#..#..
...#.......#.###..#..
...#.......#......#..
...........########..
.....................

7

Hint

Explanation for Sample 1:

Go straight, then turn left $3$ times, and finally turn right to reach F. If you go straight first and then turn right $2$ times, the cost will be $10$.

Explanation for Sample 2:

The cheapest path costs $7$: turn left immediately, go straight, turn left at the first intersection, then turn right.

For $100\%$ of the testdata: $4 \leq h,w \leq 30$.

It is guaranteed that there is exactly one start and one finish on the map, and that there exists a reachable path between them. It is also guaranteed that the outermost border of the map consists entirely of obstacles.

Translated by ChatGPT 5