Civilization
In the computer game "Civilization" version 1, the world map is a rectangular grid divided into squares. Each square can be one of three types of terrain: field, forest, or water. A settler moves across this map, taking one unit of time to move into a field square, two units of time to move into a forest square, and cannot move into a water square.
Your task is to guide a settler to a specific location where a city needs to be built to conquer the world as quickly as possible. Determine the shortest route for the settler to reach the city construction site, minimizing the time taken. The settler can move to any adjacent square that shares a side with the current square.
Input
The input begins with two natural numbers N and M, each not exceeding 1000, representing the dimensions of the world map (N is the number of rows, M is the number of columns). Following this, the coordinates of the settler's starting position are provided as x and y, where x is the row number and y is the column number (1 ≤ x ≤ N, 1 ≤ y ≤ M). Rows are numbered from top to bottom, and columns from left to right. Similarly, the coordinates of the destination square are given.
The map description follows, consisting of N rows, each containing M characters. Each character can be "." (dot) for a field, "W" for a forest, or "#" for water. It is guaranteed that both the starting and destination squares are not water.
Output
On the first line of the output, print the total time units required for the settler to reach the destination (moving into a field takes 1 time unit, and moving into a forest takes 2 time units). On the second line, print the sequence of moves as a string of characters, where each character is one of "N" (up), "E" (right), "S" (down), or "W" (left). If there are multiple shortest routes, any one of them can be printed.
If it is impossible for the settler to reach the destination square from the starting square, print -1.