5500: 汽车训练(car)

小王最近编程能力得到了飞速提升，他为自己的智能汽车编写了程序。他需要训练智能汽车让它按照指定要求移动。小王把智能汽车放在一个 N×M 的网格里并且他随机把格子的某些放置上不可以移动的障碍物。

小王把智能汽车放在网格中心的格点上，他现在要训练智能汽车让球花最少时间到达指定位置。

智能汽车本身也有自己的直径，所以有障碍物的格子的四个格点智能汽车都不能到达。

智能汽车有固定可执行的指令，每个指令所需要的执行时间为 1 秒。可以执行的指令如下：

向正前方行走 1 步（Step1）；

向正前方行走 2 步（Step2）；

向正前方行走 3 步（Step3）；

向左转（Left）；

向右转（Right）。

智能汽车要保证整个都在网格里才能执行程序，请你帮忙计算一下智能汽车完成任务所需的最少时间。

第一行为两个正整数 N, M (1≤N, M≤1000)，表示网格的大小。

接下来 N 行 M 列是网格的具体情况，0 表示无障碍，1 表示有障碍。

接下来有一行 4 个整数 x1, y1, x2, y2 和 1 个大写字母，分别为起始点 (x1, y1) 和目标点 (x2, y2) 的左上角网格的行与列。大写字母表示起始时的面对方向（东：E，南：S，西：W，北：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