pascal 搬重物

来源：百度知道 编辑：UC知道 时间：2024/04/29 06:37:24
pascal机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N*M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动1步（Creep）；向前移动2步（Walk）；向前移动3步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。

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

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

样例
ROBOT.IN
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

ROBOT.OUT
12

可以考虑一下用广度优先搜索
输出范例因该是7吧!
先转到东,再转到北-->2S
前进三步,前进两步-->2S
转到东-->1S
前进三步,前进两步到达-->2S
所以最少只须2+2+1+2=7S
下面给出我编的源程序(选了几组数据测试了一下通过了)
program zhangaiwu;
type
re=record
x,y:integer;
d:char;
end;
var
a:array[0..5000]of re;{队列}
l:array[0..50,0..50]of integer;{网格}
b:array[1..50,1..50]of boolean;{判断是否到过}
yes:array[1..50,1..50,1..4]of boolean;{判断方向是否转到过 1234分别是NSWE}
m,n,x0,y0,d0,x1,y1,closez,open,h,en,d1,d2,d3:integer;{closez,open 分别为队尾 队首指针,x0,y0,x1,y1,为始末坐标}
c,g:char;
procedure print;
forward;
procedure int;
var i,j:Integer;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt');rewrite(output);
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do read(l[i,j]);
readln;<