题目描述

某自动化仓库正在使用一台球形搬运机器人运送货物。仓库可以看作一个 $N \times M$ 的网格，部分格子设有不可通过的障碍物。

机器人的中心始终位于格点上，其直径为 $1.6$ 米，因此机器人实际占据中心周围的 $2 \times 2$ 个格子。输入中给出的起始位置和目标位置均为机器人所占 $2 \times 2$ 区域的左上角坐标。

机器人可以执行以下指令（每条指令耗时 $1$ 秒）：

• 向前移动 $1$ 步（Creep）；
• 向前移动 $2$ 步（Walk）；
• 向前移动 $3$ 步（Run）；
• 向左转（Left）；
• 向右转（Right）。

移动过程中，机器人占据的 $2 \times 2$ 区域不得包含任何障碍物，也不得超出仓库边界。起始时机器人有一个面朝方向，到达目标位置时面朝方向任意。

请计算机器人完成任务所需的最少时间。若无法到达，输出 $-1$。

输入格式

第一行两个正整数 $N, M$（$1 \le N, M \le 50$），表示仓库的行数和列数。

接下来 $N$ 行，每行 $M$ 个数字（$0$ 或 $1$），$0$ 表示无障碍，$1$ 表示有障碍，数字之间用空格隔开。

接下来一行 $4$ 个整数和 $1$ 个大写字母，依次为起始位置和目标位置的左上角行列坐标（行与列均从 $1$ 开始编号），以及起始时的面朝方向（$\tt E$ 东、$\tt S$ 南、$\tt W$ 西、$\tt N$ 北），各值之间用空格隔开。

输出格式

一个整数，表示机器人完成任务所需的最少时间。若无法到达目标位置，输出 $-1$。

样例

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S

12