tyvj/tyvj1074.pas

   1 const
   2 way : array [1..8,1..2] of longint=((-2,-1),(-2,1),(-1,2),(1,2),
   3                                   (2,1),(2,-1),(1,-2),(-1,-2));
   4 var
   5    a                                : array [-1..150,-1..150] of char;
   6    queue                            : array [0..100000] of record
   7                                          x,y                : longint;
   8                                       end;
   9    father                           : array [0..100000] of longint;
  10    endqueue                         : record
  11                                          x,y : longint;
  12                                       end;
  13    i,j,m,n,head,tail,ans            : longint;
  14
  15 function check(x,y : longint):boolean;
  16 begin
  17    check:=false;
  18    if (a[x,y]='.') then exit(true);
  19 end;
  20
  21 begin
  22    readln(m,n);
  23    for i:=1 to n do
  24    begin
  25       for j:=1 to m do
  26       begin
  27          read(a[i,j]);
  28          if a[i,j]='K' then begin queue[1].x:=i; queue[1].y:=j; a[i,j]:='.'; end;
  29          if a[i,j]='H' then begin endqueue.x:=i; endqueue.y:=j; a[i,j]:='.'; end;
  30       readln;
  31       end;
  32    end;
  33    head:=0; tail:=1;
  34    while head<tail do
  35    begin
  36       inc(head);
  37       for i:=1 to 8 do
  38          if check(queue[head].x+way[i,1],queue[head].y+way[i,2]) then
  39          begin
  40             inc(tail);
  41             queue[tail].x:=queue[head].x+way[i,1];
  42             queue[tail].y:=queue[head].y+way[i,2];
  43             father[tail]:=head;
  44             if (queue[tail].x=endqueue.x) and (queue[tail].y=endqueue.y) then break;
  45          end;
  46    end;
  47    i:=tail; ans:=0;
  48    while i<>1 do
  49    begin
  50       i:=father[tail];
  51       inc(ans);
  52    end;
  53 end.