Problem Description

The city street toll system has recently been established. A car pays $1 for each left turn and $5 for each right turn. U-turns are only allowed when there are no paths available for moving forward, left turn, or right turn, and each U-turn costs $10.

Given a city map, you are required to find the least expensive path from the starting point to the ending point. Fortunately, all roads are aligned in the cardinal directions: north, south, west, or east.

Input Format

The input format is as follows:

1. The first line contains two integers, the height $h$ and width $w$ of the map.
2. The following $h$ lines, each containing $w$ characters, will be one of the following:

• . represents an obstacle area.
• # represents a road.
• E represents the starting point with the car facing east.
• W represents the starting point with the car facing west.
• N represents the starting point with the car facing north.
• S represents the starting point with the car facing south.
• F represents the destination.

Output Format

Output a single integer, which is the cost of the cheapest path.

Sample Input and Output

Sample Input #1

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

Sample Output #1

8

Sample Input #2

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

Sample Output #2

7

Notes

Explanation of Sample #1:

Go straight, then turn left three times, and finally turn right to the destination F. If you go straight and then turn right twice, the cost will be $10$.

Explanation of Sample #2:

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

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

The data guarantees that there is only one starting point and one ending point on the map, and there is a traversable path between them. Additionally, the outermost layer of the map is guaranteed to be obstacles.

见题面 Input 部分

见题面 Output 部分