Civilization#4455
In version of the computer game "Civilization", the world map is represented as a rectangle divided into squares. Each square can have one of several types of terrain; for simplicity, consider three types: field, forest, and water. A settler moves across the map, with each movement into a square costing a certain number of time units: moving into a field requires unit, moving into a forest requires units, and moving into water is impossible.
You have one settler, and you have designated a location at which you want to build a city in order to conquer the world as quickly as possible. Find the shortest route for the settler to reach the city construction site that minimizes the total time taken. At each step, the settler can move to an adjacent square sharing a side with their current square.
The first line contains two natural numbers and (1 \le N, M \le 1000) — the dimensions of the world map ( is the number of rows, is the number of columns).
The second line contains the coordinates of the settler's initial position: and , where is the row number and is the column number (1 \le x \le N, 1 \le y \le M).
Rows are numbered from top to bottom, columns from left to right.
The third line contains the coordinates of the destination square in the same format.
The following lines each contain characters describing the world map. Each character is one of: - "." — a field, - "W" — a forest, - "#" — water.
It is guaranteed that both the starting and destination squares are not water.
On the first line, print the minimum number of time units required for the settler to reach the destination (moving into a field costs unit, moving into a forest costs units).
On the second line, print as a single string the sequence of moves to be taken: each character must be one of "N" (up), "E" (right), "S" (down), or "W" (left). If there are multiple shortest routes, output any one of them.
If it is impossible to reach the destination from the starting square, output .
Example 1