[eJOI2019] Awesome Arrowland Adventure
题目描述
你现在在一个大小为 $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```;
如果有,输出一个整数表示需要旋转的最少次数。
输入输出样例
输入样例 #1
3 3
EES
SSW
ESX
输出样例 #1
3
输入样例 #2
3 3
EES
SSW
EEX
输出样例 #2
0
输入样例 #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$ 次。
---
#### 数据规模与约定
**本题采用多测试点捆绑测试,共有 $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](https://www.ejoi2019.si) Problem F [Awesome Arrowland Adventure](https://www.ejoi2019.si/static/media/uploads/tasks/adventure-isc(1).pdf)
题面翻译:@[```_Wallace_```](https://www.luogu.com.cn/user/61430)(如果觉得这个翻译令人谔谔,欢迎提供新翻译)