7456

Hangben @ 2016-10-23 18:27:26

by Hangben @ 2016-10-23 18:28:22

program cowescape;
  var
    m,i,j,aa,bb,x,y,t:longint;
    a,b:array[1..5] of longint;
    map:array[0..1000,0..1000] of longint;
procedure tr(xxx,yyy,time:longint);
  var
    aa,bb,k:longint;
  begin
    if map[xxx,yyy]=-1 then
      begin
        writeln(time);
        halt;
      end;
    for k:=1 to 4 do
      begin
        aa:=xxx+a[k];
        bb:=yyy+b[k];
        if (aa<0) or (bb<0) then continue;
        if (map[aa,bb]>time+1) or (map[aa,bb]=-1) then tr(aa,bb,time+1);
      end;
  end;
function min(xx,yy:longint):longint;
  begin
    if xx<yy then exit(xx) else exit(yy);
  end;
  begin
    readln(m);
    a[1]:=0;
    a[2]:=1;
    a[3]:=0;
    a[4]:=-1;
    a[5]:=0;
    b[1]:=1;
    b[2]:=0;
    b[3]:=-1;
    b[4]:=0;
    b[5]:=0;
    fillchar(map,sizeof(map),-1);
    for i:=1 to m do
      begin
        readln(x,y,t);
        for j:=1 to 5 do
          begin
            aa:=x+a[j];
            bb:=y+b[j];
            if (aa<0) or (bb<0) then continue;
            if (map[aa,bb]<>-1) then map[aa,bb]:=min(map[aa,bb],t)
            else map[aa,bb]:=t;
          end;
      end;
    tr(0,0,0);
    writeln(-1);
end.

by Hangben @ 2016-10-23 18:29:06

另：这题有什么优化剪枝？