maze1.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 82 行

{
ID:maigoak1
PROG:maze1
}

program maze1;
const
  maxh=100;
  maxw=38;
var
  fin,fout:text;
  up,down,left,right:array[1..maxh,1..maxw]of boolean;
  dist:array[1..maxh,1..maxw]of integer;
  q:array[1..maxh*maxw+1]of record
      x,y:integer;
    end;
  h,w,i,j,front,rear,px,py:integer;
  c:char;
procedure push(a,b,d:integer);
  begin
    if dist[a,b]=0 then begin
      inc(rear);
      q[rear].x:=a;
      q[rear].y:=b;
      dist[a,b]:=d;
    end;
  end;
begin
  fillchar(up,sizeof(up),0);
  fillchar(down,sizeof(down),0);
  fillchar(left,sizeof(left),0);
  fillchar(right,sizeof(right),0);
  fillchar(dist,sizeof(dist),0);

  assign(fin,'maze1.in');
  reset(fin);
  readln(fin,w,h);
  for i:=1 to h*2+1 do begin
    for j:=1 to w*2+1 do begin
      read(fin,c);
      write(c);
      if c=' ' then
        if odd(i) and (not odd(j)) then begin
          if i<=h*2 then up[i div 2+1,j div 2]:=true;
          if i>1 then down[i div 2,j div 2]:=true;
        end
        else if (not odd(i)) and odd(j) then begin
          if j<=w*2 then left[i div 2,j div 2+1]:=true;
          if j>1 then right[i div 2,j div 2]:=true;
        end;
    end;
    readln(fin);
    writeln;
  end;
  close(fin);

  front:=0;rear:=0;
  for i:=1 to h do begin
    if left[i,1] then push(i,1,1);
    if right[i,w] then push(i,w,1);
  end;
  for i:=1 to w do begin
    if up[1,i] then push(1,i,1);
    if down[h,i] then push(h,i,1);
  end;

  repeat
    inc(front);
    px:=q[front].x;py:=q[front].y;
    if (px>1) and up[px,py] then push(px-1,py,dist[px,py]+1);
    if (px<h) and down[px,py] then push(px+1,py,dist[px,py]+1);
    if (py>1) and left[px,py] then push(px,py-1,dist[px,py]+1);
    if (py<w) and right[px,py] then push(px,py+1,dist[px,py]+1);
  until front=rear;

  assign(fout,'maze1.out');
  rewrite(fout);
  writeln(fout,dist[px,py]);
  close(fout);
end.