P6233 [eJOI 2019] 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)$ 的路径，如果有，求出最小需要的旋转次数。

无

无

#### 样例解释 【样例 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)（如果觉得这个翻译令人谔谔，欢迎提供新翻译）