题目描述

你现在在一个大小为 $m$ 行（行编号从 $0$ 开始，从上往下一直到 $m-1$） $n$ （列编号从 $0$ 开始，从左往右一直到 $n-1$）列的矩阵中。你的初始位置为 $(0,0)$。（$(r,c)$ 表示矩阵中第 $r$ 行，第 $c$ 列的位置）

你需要走到位置 $(m-1,n-1)$ 处。这个矩阵非常神奇——在矩阵的某些格子上有一个箭头。 箭头只可能有四种方向：北（向上），东（向右），南（向下），西（向左）。箭头分布在整个矩阵之上，形成了箭头矩阵。

当你在某一个位置时，假如这个位置不在矩形（左上角 $(0,0)$，右下角 $(m-1,n-1)$）范围内或这个位置没有箭头，那么你会一直停留于此，永远无法到达终点。如果此处有箭头，那么你将会向这个箭头的方向走一格。

但显然，你不一定能够在初始的箭头矩阵上找到一条从 $(0,0)$ 到 $(m-1,n-1)$ 的路径。为了找到这样一条路径，你可以一次将箭头矩阵中某一个箭头 顺时针 旋转 $90$ 度。通过几次的旋转，你可能会找到一条路径。

请你判断是否可以通过旋转来得到一条从 $(0,0)$ 到 $(m-1,n-1)$ 的路径，如果有，求出最小需要的旋转次数。

输入格式

第一行：两个整数 $m,n$ ，表示矩阵的大小；

接下来 $m$ 行，每行一个长度为 $n$ 的字符串，表示箭头矩阵中这一行的箭头的信息。字符串只可能包含 $5$ 种字符：W，E，N，S，X。它们分别表示：西，东，北，南，没有箭头。

输出格式

如果没有可以找到路径的旋转方案，输出 -1；

如果有，输出一个整数表示需要旋转的最少次数。

3 3
EES
SSW
ESX

3

3 3
EES
SSW
EEX

0

3 4
EXES
WSNS
XNNX

4

提示

样例解释

【样例 1 解释】

• 一个可行的解是，将位置 $(1,2)$ 的 W 旋转 $3$ 次变成 S。

【样例 2 解释】

• 不需要任何旋转就可以。

【样例 3 解释】

• 在 $(0,0)$ 处旋转 $1$ 次，在 $(1,0)$ 处旋转 $2$ 次，在 $(2,1)$ 处旋转 $1$ 次。

数据规模与约定

本题采用多测试点捆绑测试，共有 $5$ 个子任务。

• Subtask 1（10 points）：$m=1$，且输入的字符矩阵只包含 E 或 X。
• Subtask 2（12 points）：$m=1$。
• Subtask 3（12 points）：$n=m=3$。
• Subtask 4（16 points）：$m=2$。
• Subtask 5（50 points）：无特殊限制。

对于 全部的测试点，保证 $1\le m,n\le 500$。

说明

原题来自：eJOI2019 Problem F Awesome Arrowland Adventure

题面翻译：@_Wallace_（如果觉得这个翻译令人谔谔，欢迎提供新翻译）