题目描述

本题译自 eJOI2019 Problem F. Awesome Arrowland Adventure

EJOI 2542 在 Arrowland 举行。Arrowland 可以描述为一个 $m$ 行（编号为 $0$ 到 $m-1$）$n$ 列（编号为 $0$ 到 $n-1$）的网格，每个单元格代表一个城市。令 $(r,c)$ 表示在第 $r$ 行第 $c$ 列的单元格。选手们住在单元格 $(0,0)$，比赛地在单元格 $(m-1,n-1)$。

Arrowland 的一个奇怪的景点是有些城市有巨大的箭头。更奇怪的是，这些箭头一次只能顺时针旋转 $90$ 度。初始时，每个箭头都指向东西南北四个方向之一。考虑到东道主国家的名字，EJOI 的组织者想要利用这些箭头。

选手们无论目前在哪里，都会盲目跟从箭头的指示前进。他们只会按照每个城市箭头的指示，从这个城市前往相邻的城市。如果他们进入的这个城市没有箭头，或者他们会离开 Arrowland，他们就会停在原地，并且永远不会到达比赛地了。因为 EJOI 的组织者想要选手们从他们的住处（单元格 $(0,0)$）到达比赛地，他们就可能需要旋转一些箭头的指向。请帮他们确定为了达成目标，最少需要旋转多少次箭头，或者无论箭头的指向是哪里，都不可能让选手到达比赛地。

输入格式

第一行包含两个整数 $m$ 和 $n$，分别表示行数和列数。

接下来 $m$ 行，每行 $n$ 个字符，表示初始箭头的朝向（N 表示向北，E 表示向东，S 表示向南，W 表示向西，X 表示这个单元格没有箭头）。最后一行的最后一个字符（即表示比赛地的字符）保证是 X。

在输入矩阵中，东西南北的方位和在通常地图中一样。因此，N 表示向上，E 表示向右，S 表示向下，W 表示向左。

输出格式

输出 EJOI 的组织者最少旋转箭头的次数。如果这个任务无法完成，输出 $-1$。

3 3
EES
SSW
ESX

3

3 3
EES
SSW
EEX

0

3 4
EXES
WSNS
XNNX

4

数据范围与提示

对于 $100\%$ 的数据，保证 $1\le m, n\le 500$。

子任务

• 子任务 $1$：保证 $m = 1$，每个字符是 E 或 X。
• 子任务 $2$：保证 $m = 1$。
• 子任务 $3$：保证 $m = n = 3$。
• 子任务 $4$：保证 $m = 2$。
• 子任务 $5$：没有附加限制。