Problem C
Conveyor Belt Inspection
Languages
en
pt
A company that makes conveyor belts keeps $n \cdot m$ of them in a warehouse that can be represented as a grid with $n$ lines and $m$ columns. Each conveyor belt occupies exactly one position on the grid and can be pointing north (N), south (S), east (E) or west (W).
If an object is at grid position $(i, j)$, in $1$ second this object will be in position $(i-1, j)$ if the conveyor belt in this position points north, $(i+1, j)$ if it points south, $(i, j-1)$ if it points east and $(i, j+1)$ if it points west. Notice that this new position can be outside the grid, in which case the object would exit the grid.
João has an internship as a conveyor belt inspector and needs to inspect all conveyor belts on the grid. This is his first internship and he has no idea what he’s doing, therefore he decides to gather insignificant information about the conveyor belts.
Let’s call $f(x)$ how many seconds it takes for an object starting on conveyor belt $x$ to either exit the grid or visit a position it already occupied. João wants to know the sum of $f(x)$ for all conveyor belts on the grid.
João is too lazy and will neither simulate the process nor write a program that does. Help him gather the information he needs.
Input
The first line of input will consist of two integers $n$ and $m$ ($1 \leq n, m \leq 10^3$), the number of lines and number of columns on the grid, respectively.
Then $n$ lines will follow. The $i$-th line will contain $m$ letters. The $j$-th letter can be N, S, E or W, and represents in which direction the conveyor belt at position $(i, j)$ is pointing.
Output
Print a single integer, the sum of $f(x)$ for all conveyor belts on the grid.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 3 WWW |
6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 3 EES NNS NWW |
73 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 3 ESN NWW NNW |
38 |
