机器人搬重物

题目描述

机器人移动学会(`RMI`)现在正尝试用机器人搬运物品。机器人的形状是一个直径$1.6$米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个 $N \times M$ 的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有:向前移动$1$步(`Creep`);向前移动2步(`Walk`);向前移动$3$ 步(`Run`);向左转(`Left`);向右转(`Right`)。每个指令所需要的时间为$1$ 秒。请你计算一下机器人完成任务所需的最少时间。

输入输出格式

输入格式


第一行为两个正整数$N,M(N,M \le 50)$,下面$N$行是储藏室的构造,$0$表示无障碍,$1$表示有障碍,数字之间用一个空格隔开。接着一行有$4$个整数和$1$个大写字母,分别为起始点和目标点左上角网格的行与列,起始时的面对方向(东$E$,南$S$,西$W$,北$N$),数与数,数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出格式


一个整数,表示机器人完成任务所需的最少时间。如果无法到达,输出$-1$。 ![](https://cdn.luogu.com.cn/upload/pic/39.png)

输入输出样例

输入样例 #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

输出样例 #1

12