P1376. 机器人路径规划

题目描述

机器人移动研究所(RMI)在本地商店使用机器人运输物品。机器人需要在商店中从一个位置移动到另一个位置时花费最少的时间。机器人只能沿着直线轨道移动，所有轨道形成矩形网格，相邻轨道间距为$1$米。

商店是$N \times M$米的矩形区域，完全被这个网格覆盖。最靠近商店边缘的轨道距离边缘正好$1$米。机器人呈圆形，直径为$1.6$米，轨道穿过机器人中心。机器人始终面向北、南、西或东四个方向之一，且只能沿面向的方向移动。方向只能在轨道交叉处改变。机器人初始位置位于轨道交叉点。

障碍物占据地面上$1m \times 1m$的区域，每个障碍物位于轨道形成的$1 \times 1$方格内。机器人运动由两个命令控制：

1. GO命令：参数$n \in \{1,2,3\}$，使机器人沿当前方向移动$n$米
2. TURN命令：参数为left或right，使机器人方向顺时针或逆时针旋转90度

每个命令执行耗时1秒。请编写程序计算机器人从起点到终点的最短时间。

输入格式

• 多个数据块组成
• 每个块首行是两个整数$M \leq 50$和$N \leq 50$
• 接下来$M$行，每行$N$个0或1（1表示障碍物，0表示空位）
• 最后一行四个整数$B1\ B2\ E1\ E2$和起始方向(north/west/south/east)
• 坐标系统：(行,列)类型，左上角(最西北)方格为$(0,0)$，右下角(最东南)为$(M-1,N-1)$
• 最后一个块仅包含"0 0"

输出格式

• 对每个输入块(除最后一个)，输出最短时间(秒)
• 若不可达则输出-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 south
0 0

样例输出

12

题目来源

Central Europe 1996