该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

智能汽车停放在网格中心的格点上，现在需要训练它在最短时间内到达指定目标位置。

由于智能汽车自身有一定直径，任何障碍物所在格子的 四个角（即四个相邻格点）都是不可到达的区域。

智能汽车可以执行以下 5 种指令，每条指令执行时间均为 1 秒：

• Step1：向当前朝向的“正前方”行走 1 步；
• Step2：向当前朝向的“正前方”行走 2 步；
• Step3：向当前朝向的“正前方”行走 3 步；
• Left：向左转 90°；
• Right：向右转 90°。

智能汽车在执行任何指令时，必须保证自身整个都在网格范围内且不与障碍物冲突。请你计算智能汽车完成从起点到终点所需的最少时间；若无法到达，则输出 $-1$。

输入格式

从文件 car.in 中读入数据。

N M
grid_1
grid_2
⋮
grid_N
x1 y1 x2 y2 D

• 第一行包含两个正整数 $N, M$（$1 \le N,M \le 10^3$），表示网格的行数和列数。

• 接下来 $N$ 行，每行 $M$ 个字符，组成网格地图：

  • 0 表示该格无障碍；
  • 1 表示该格有障碍。

• 最后一行包含四个整数和一个大写字母，格式为

  x1 y1 x2 y2 D
  

  • $(x_1,y_1)$：起点所在网格的左上角行、列编号；
  • $(x_2,y_2)$：终点所在网格的左上角行、列编号；
  • $D\in\{\text{E},\text{S},\text{W},\text{N}\}$：起始朝向，分别代表“东、南、西、北”。

• 起点、终点编号均满足 $1\le x_i\le N$，$1\le y_i\le M$。

• 数与数，数与字母之间均用一个空格隔开

• 起点和终点可以相同；终点朝向无要求。

输出格式

将结果写入文件 car.out，输出一个整数，为智能汽车完成任务的最少用时（秒）。若无法到达终点，则输出 $-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

样例说明：

如图所示，白色格子无障碍、黑色格子有障碍。最短路径共 7 步前进（7 秒），途中 5 次转向（5 秒），总时间 $7+5=12$ 秒。

数据范围

• 对所有测试点，均满足

  $5 \le N, M \le 10^3.$

• 测试点细分：