ac1155.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1155;
const
  maxsize=15;
  bit:array[0..10]of word=(0,1,2,4,8,16,32,64,128,256,512);
  maxstatus=1023;
  dx:array[1..4]of shortint=(-1,1,0,0);
  dy:array[1..4]of shortint=(0,0,-1,1);
var
  go:array[1..maxsize,1..maxsize,1..4]of byte;{0 for wall,99 for ok}
  key:array[1..maxsize,1..maxsize]of word;
  q:array[1..sqr(maxsize)*maxstatus]of record x,y:byte;s:word;end;
  dist:array[1..maxsize,1..maxsize,0..maxstatus]of cardinal;
  n,m,p,i,j,f,r,x1,y1,x2,y2:longint;
procedure bfs;
  begin
    fillchar(dist,sizeof(dist),255);
    f:=0;r:=1;with q[1] do begin x:=1;y:=1;s:=0;end;dist[1,1,0]:=0;
    repeat
      inc(f);x1:=q[f].x;y1:=q[f].y;
      j:=q[f].s or key[x1,y1];
      for i:=1 to 4 do
        if (go[x1,y1,i]=99) or (j and bit[go[x1,y1,i]]>0) then begin
          x2:=x1+dx[i];y2:=y1+dy[i];
          if dist[x2,y2,j]<maxlongint then continue;
          if (x2=n) and (y2=m) then begin writeln(dist[x1,y1,q[f].s]+1);exit;end;
          inc(r);with q[r] do begin x:=x2;y:=y2;s:=j;end;dist[x2,y2,j]:=dist[x1,y1,q[f].s]+1;
        end;
    until f=r;
    writeln('Poor Angel!');
  end;
begin
  repeat
    read(n,m,p);
    for i:=1 to n do
      for j:=1 to m do begin
        if i=1 then go[i,j,1]:=0 else go[i,j,1]:=99;
        if i=n then go[i,j,2]:=0 else go[i,j,2]:=99;
        if j=1 then go[i,j,3]:=0 else go[i,j,3]:=99;
        if j=m then go[i,j,4]:=0 else go[i,j,4]:=99;
      end;
    read(f);
    for i:=1 to f do begin
      read(x1,y1,x2,y2,r);
      if x1=x2 then
        if y1<y2 then begin
          go[x1,y1,4]:=r;go[x2,y2,3]:=r;
        end
        else begin
          go[x1,y1,3]:=r;go[x2,y2,4]:=r;
        end
      else
        if x1<x2 then begin
          go[x1,y1,2]:=r;go[x2,y2,1]:=r;
        end
        else begin
          go[x1,y1,1]:=r;go[x2,y2,2]:=r;
        end;
    end;
    fillchar(key,sizeof(key),0);
    read(f);
    for i:=1 to f do begin
      read(x1,y1,r);
      key[x1,y1]:=key[x1,y1] or bit[r];
    end;
    if n+m=2 then writeln(0) else bfs;
  until seekeof;
end.