竞赛基础算法

【题目描述】机器人搬重物（robot）

机器人形状是一个直径1个单位的球，被用于在一个储藏室中搬运货物。储藏室是一个N×M的网格，每个格子为正方形，边长1个单位，有些格子为不可移动的障碍（0表示无障碍，1表示有障碍）。机器人的中心总是在格点上，控制机器人行走有五种指令，分别是：向前移动1步；向前移动2步；向前移动3步；向左转；向右转。每个指令所需要的时间为1秒。现给出机器人的起点和当前面向的方向以及目标终点，请计算出机器人完成任务所需的最少时间。

图9.

【输入格式】

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

【输出格式】

一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出−1。

【输入样例】

10 9

1 0 0 0 0 0 0 0 0  

0 0 0 0 0 0 0 0 0  

0 0 0 0 0 1 0 0 0  

0 0 1 0 0 0 1 0 0  

0 0 1 0 0 0 0 0 0  

0 0 0 1 0 0 0 0 0  

0 0 0 0 1 0 0 0 1  

1 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 1 1

0 0 0 1 1 1 1 0 0

2 2 7 7 W

【输出样例】

12