题解 P1374 【进攻幽暗城】

courage · 2013-07-16 10:40:34 · 题解

朴素的BFS，这是我的Pascal代码

type  
  rec1=record x,y:longint;end;  
  rec2=record t,x,y,L:longint;end;  
var  
  a:array[0..51,0..51] of char;  
  b,c:array[0..100] of rec1;  
  g:array[0..4,1..2] of longint=((0,0),(-1,0),(1,0),(0,-1),(0,1));  
  f:array[1..100000] of rec2;  
  n,m,ss,d,i,j,k,x1,x2,y1,y2,sta,x,y,t:longint;  
  s:string;  
procedure print(x:longint);  
begin  
  writeln(x);  
  halt;  
end;  
function safe(t,x,y:longint):boolean;  
begin  
  if (x-b[t].x)*(x-b[t].x)+(y-b[t].y)*(y-b[t].y)<=d*d then exit(true);  
  exit(false);  
end;  
function next(x:longint):longint;  
begin  
  inc(x);  
  if x>100000 then x:=1;  
  exit(x);  
end;  
procedure go(var x,y:longint;p:longint);  
begin  
  sta:=0;  
  if a[x+g[p,1],y+g[p,2]]='1' then exit;  
  x:=x+g[p,1];  
  y:=y+g[p,2];  
  sta:=p;  
end;  
begin  
  for i:=0 to 51 do  
    for j:=0 to 51 do a[i,j]:='1';  
  readln(n,m,ss,d);  
  for i:=1 to n do  
    begin  
      for j:=1 to m do read(a[i,j]);  
      readln;  
    end;  
  readln(x1,y1,x2,y2);  
  readln(s);  
  b[0].x:=x1;b[0].y:=y1;  
  c[0].x:=x2;c[0].y:=y2;  
  if (x1=x2)and(y1=y2) then print(0);  
  for i:=1 to 100 do  
    begin  
      go(x1,y1,ord(s[(i-1) mod length(s)+1])-48);  
      b[i].x:=x1;b[i].y:=y1;  
    end;  
  readln(s);  
  for i:=1 to 100 do  
    begin  
      go(x2,y2,ord(s[(i-1) mod length(s)+1])-48);  
      c[i].x:=x2;c[i].y:=y2;  
    end;  
  i:=1;  
  j:=1;  
  f[1].t:=0;  
  f[1].x:=b[0].x;  
  f[1].y:=b[0].y;  
  f[1].L:=ss;  
  while i<>next(j) do  
    begin  
      t:=f[i].t+1;  
      x:=f[i].x;  
      y:=f[i].y;  
      if safe(t,x,y) or (f[i].L>0) then  
        begin  
          j:=next(j);  
          f[j].x:=x;  
          f[j].y:=y;  
          f[j].t:=t;  
          if (x=c[t].x)and(y=c[t].y) then print(t);  
          if safe(t,x,y) then f[j].L:=ss else f[j].L:=f[i].L-1;  
        end;  
      for k:=1 to 4 do  
        begin  
          x:=f[i].x;  
          y:=f[i].y;  
          go(x,y,k);  
          if sta=0 then continue;  
          if not(safe(t,x,y) or (f[i].L>0)) then continue;  
          j:=next(j);  
          f[j].x:=x;  
          f[j].y:=y;  
          f[j].t:=t;  
          if (x=c[t].x)and(y=c[t].y) then print(t);  
          if safe(t,x,y) then f[j].L:=ss else f[j].L:=f[i].L-1;  
        end;  
      i:=next(i);  
    end;  
end.