记录编号	117519	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Oct07] 障碍训练场	最终得分	100
用户昵称	筽邝	是否通过	通过
代码语言	Pascal	运行时间	0.083 s
提交时间	2014-08-30 11:21:04	内存使用	11.81 MiB

program cojs161;{24}
const
  dx:array[1..4]of longint=(1,-1,0,0);
  dy:array[1..4]of longint=(0,0,1,-1);
  maxn=110;
type
  qnode=record
    x,y,z:longint;
  end;
var
  ans,sx,sy,tx,ty,n,i:longint;
  a:array[0..maxn,0..maxn]of boolean;
  f:array[0..maxn,0..maxn,1..4]of longint;
  q:array[0..1000000]of qnode;

procedure init;
var
  s:string;
  i,j:longint;
begin
  readln(n);
  for i:=1 to n do
  begin
    readln(s);
    for j:=1 to n do
    case s[j] of
    '.':a[i,j]:=true;
    'x':a[i,j]:=false;
    'A':begin
          a[i,j]:=true;
          sx:=i;
          sy:=j;
        end;
    'B':begin
          a[i,j]:=true;
          tx:=i;
          ty:=j;
        end;
    end;
  end;
end;

procedure bfs;
var
  front,tail,i,j,k,xx,yy,zz:longint;
  v:array[0..maxn,0..maxn,1..4]of boolean;
begin
  fillchar(v,sizeof(v),false);
  for i:=1 to n do
  for j:=1 to n do
  for k:=1 to 4 do
    f[i,j,k]:=maxlongint div 2;
  front:=0; tail:=0;
  for i:=1 to 4 do
  begin
    inc(tail);
    q[tail].x:=sx; q[tail].y:=sy; q[tail].z:=i;
    v[q[tail].x,q[tail].y,q[tail].z]:=true;
    f[q[tail].x,q[tail].y,q[tail].z]:=0;
  end;
  while front<>tail do
  begin
    inc(front);
    for i:=1 to 4 do
    begin
      xx:=q[front].x+dx[i];
      yy:=q[front].y+dy[i];
      if i=q[front].z then zz:=f[q[front].x,q[front].y,q[front].z]
      else zz:=f[q[front].x,q[front].y,q[front].z]+1;
      if (xx<1)or(xx>n)or(yy<1)or(yy>n)or(not a[xx,yy]) then continue;
      if zz<f[xx,yy,i] then
      begin
        f[xx,yy,i]:=zz;
        if not v[xx,yy,i] then
        begin
          inc(tail);
          q[tail].x:=xx; q[tail].y:=yy; q[tail].z:=i;
          v[xx,yy,i]:=true;
        end;
      end;
    end;
    v[q[front].x,q[front].y,q[front].z]:=false;
  end;
end;

begin
assign(input,'obstacle.in');reset(input);
assign(output,'obstacle.out');rewrite(output);

  init;
  bfs;
  ans:=maxlongint;
  for i:=1 to 4 do
    if f[tx,ty,i]<ans then ans:=f[tx,ty,i];
  writeln(ans);

close(input);close(output);
end.