Magic Arrow Matrix

You are given an (m \times n) matrix. The rows are numbered from (0) to (m-1) (top to bottom) and columns from (0) to (n-1) (left to right). Some cells in the matrix contain an arrow that points in one of the four directions: north, east, south, or west (denoted by the characters N, E, S, W). Other cells are empty (denoted by a dot '.') and cannot be traversed. You start at cell ((0,0)) and wish to reach cell ((m-1,n-1)). From any cell ((r,c)) that contains an arrow, you follow the arrow to move one cell in that direction. However, if the cell either does not lie inside the matrix or does not have an arrow, you become stuck and will never reach the destination.\n\nSince the initial configuration might not allow a path from ((0,0)) to ((m-1,n-1)), you are allowed to modify the matrix: in one operation, you may choose an arrow cell and rotate its arrow clockwise by (90^\circ) (each rotation counts as one operation). You may rotate the same arrow multiple times, with the cost accumulating accordingly.\n\nYour task is to determine whether it is possible to obtain a configuration that allows a path from ((0,0)) to ((m-1,n-1)). If possible, output the minimum number of rotations required; otherwise, output (-1).

inputFormat

The first line contains two integers (m) and (n) (the number of rows and columns, respectively).\nThe next (m) lines each contain a string of length (n) representing the matrix. Each character is one of: (N), (E), (S), (W) (denoting an arrow) or a dot ( . ) (denoting an empty cell with no arrow).\n\nNote: Only cells that originally contain an arrow can be rotated. The destination cell ((m-1,n-1)) does not need to have a working arrow since once you reach it, the process stops.

outputFormat

Output a single integer: the minimum number of rotations needed to enable a path from ((0,0)) to ((m-1,n-1)). If it is impossible, output (-1).

sample

2 2
ES
NN

0