You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

箭头

题目描述

给定一个 $n$ 行 $m$ 列的矩阵，你在左上角，需要走到右下角。矩阵中有些格子里有箭头，箭头会指向上下左右四个方向，当你在有箭头的格子中时，你必须沿着箭头的方向前进 $1$ 格，然后根据下一格有没有箭头来继续前进。当你在没有箭头的格子中，或者你走出了方阵时，你将无法继续前进，永远到达不了右下角。

为了能顺利从左上角到达右下角，你可以一次将箭头矩阵中某一个箭头 顺时针 旋转 $90$ 度。通过几次的旋转，你可能会找到一条路径。

请你判断是否可以通过旋转来得到一条从左上角到右下角的路径，如果有，求出最小需要的旋转次数。

输入格式

第一行：两个整数 $n,m$ ，表示矩阵的大小。接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示箭头矩阵中这一行的箭头的信息。字符串只可能包含 $5$ 种字符：W，E，N，S，X。它们分别表示：左，右，上，下，空格。

输出格式

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

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

样例 #1

样例输入 #1

3 3
EES
SSW
ESX

样例输出 #1

3

样例 #2

样例输入 #2

3 3
EES
SSW
EEX

样例输出 #2

0

样例 #3

样例输入 #3

3 4
EXES
WSNS
XNNX

样例输出 #3

4

提示

样例解释

【样例 1 解释】

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

【样例 2 解释】

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

【样例 3 解释】

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

数据规模与约定

对于所有数据，保证 $1\le m,n\le 500$。

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