POJ2222 Deeper Blue — DFS

Note: 本文最初于 2011年02月26日 星期六 17:41 在 hi.baidu.com/lydrainbowcat 发表。

因为今天下午实在是比较2，所以做了Poj2222，这题也挺2。直接爆搜（枚举）。目前程序在所有Pascal提交代码中排第2。

Source Code

Problem: 2222		User: lydliyudong
Memory: 904K		Time: 16MS
Language: Pascal		Result: Accepted

• Source Code

const
 bkx:array[1..9]of integer=(0,-1,-1,-1,0,0,1,1,1);
 bky:array[1..9]of integer=(0,-1,0,1,-1,1,-1,0,1);
 bnx:array[1..9]of integer=(0,-1,-2,-1,-2,1,2,1,2);
 bny:array[1..9]of integer=(0,-2,-1,2,1,-2,-1,2,1);
var
 s:string; space:char;
 a:array[0..11,0..11]of char;
 f:array[-1..12,-1..12]of longint;
 b,c:array[0..20]of longint;
 d:array[0..20]of char;
 n,m,i,j,tot,ans:longint;

procedure scanf;
 begin
  tot:=0;
  readln(s);
  readln(m);
  readln(n);
  for i:=1 to n do
   begin
    j:=0;
    while j<m do
     begin
      inc(j);
      read(a[i,j]);
      if a[i,j]<>'E' then
       begin inc(tot); b[tot]:=i; c[tot]:=j; d[tot]:=a[i,j]; end;
      if j<m then read(space);
     end;
    readln;
   end;
  readln(s);
 end;

function go(x,y:longint):boolean;
 begin
  if (x>=1)and(y>=1)and(x<=n)and(y<=m) then exit(false) else exit(true);
 end;

function bk(now:longint):boolean;
 var
  x,y,i:longint;
 begin
  x:=b[now]; y:=c[now];
  for i:=2 to 9 do
   if not go(x+bkx[i],y+bky[i]) and(a[x+bkx[i],y+bky[i]]='P') then exit(false);
  exit(true);
 end;

function bn(now:longint):boolean;
 var
  x,y,i:longint;
 begin
  x:=b[now]; y:=c[now];
  for i:=2 to 9 do
   if not go(x+bnx[i],y+bny[i]) and(a[x+bnx[i],y+bny[i]]='P') then exit(false);
  exit(true);
 end;

function br(now:longint):boolean;
 var
  x,y:longint;
 begin
  x:=b[now]; y:=c[now];
  repeat dec(x); if a[x,y]='P' then exit(false); until x<=1;
  x:=b[now]; y:=c[now];
  repeat inc(x); if a[x,y]='P' then exit(false); until x>=n;
  x:=b[now]; y:=c[now];
  repeat dec(y); if a[x,y]='P' then exit(false); until y<=1;
  x:=b[now]; y:=c[now];
  repeat inc(y); if a[x,y]='P' then exit(false); until y>=m;
  exit(true);
 end;

function bb(now:longint):boolean;
 var
  x,y:longint;
 begin
  x:=b[now]; y:=c[now];
  repeat dec(x); dec(y); if a[x,y]='P' then exit(false); until (x<=1)or(y<=1);
  x:=b[now]; y:=c[now];
  repeat inc(x); inc(y); if a[x,y]='P' then exit(false); until (x>=n)or(y>=m);
  x:=b[now]; y:=c[now];
  repeat dec(y); inc(x); if a[x,y]='P' then exit(false); until (y<=1)or(x>=n);
  x:=b[now]; y:=c[now];
  repeat inc(y); dec(x); if a[x,y]='P' then exit(false); until (y>=m)or(x<=1);
  exit(true);
 end;

procedure fk(now,num:longint);
 var
  x,y,i:longint;
 begin
  x:=b[now]; y:=c[now];
  for i:=1 to 9 do
   inc(f[x+bkx[i],y+bky[i]],num);
 end;

procedure fn(now,num:longint);
 var
  x,y,i:longint;
 begin
  x:=b[now]; y:=c[now];
  for i:=1 to 9 do
   inc(f[x+bnx[i],y+bny[i]],num);
 end;

procedure fr(now,num:longint);
 var
  x,y:longint;
 begin
  x:=b[now]; y:=c[now];
  repeat inc(f[x,y],num); dec(x); until x<1;
  x:=b[now]; y:=c[now];
  repeat inc(f[x,y],num); inc(x); until x>n;
  x:=b[now]; y:=c[now];
  repeat inc(f[x,y],num); dec(y); until y<1;
  x:=b[now]; y:=c[now];
  repeat inc(f[x,y],num); inc(y); until y>m;
 end;

procedure fb(now,num:longint);
 var
  x,y:longint;
 begin
  x:=b[now]; y:=c[now];
  repeat inc(f[x,y],num); dec(x); dec(y); until (x<1)or(y<1);
  x:=b[now]; y:=c[now];
  repeat inc(f[x,y],num); inc(x); inc(y); until (x>n)or(y>m);
  x:=b[now]; y:=c[now];
  repeat inc(f[x,y],num); dec(y); inc(x); until (y<1)or(x>n);
  x:=b[now]; y:=c[now];
  repeat inc(f[x,y],num); inc(y); dec(x); until (y>m)or(x<1);
 end;

procedure dfs(now,del:longint);
 begin
  if now=tot+1 then
   begin
    if del<ans then ans:=del;
    exit;
   end;
  dfs(now+1,del+1);
  case d[now] of
   'K':if bk(now) and(f[b[now],c[now]]<=0) then
    begin
     fk(now,1);
     a[b[now],c[now]]:='P';
     dfs(now+1,del);
     a[b[now],c[now]]:='K';
     fk(now,-1);
    end;
   'Q':if bb(now) and br(now) and(f[b[now],c[now]]<=0) then
     begin
      fr(now,1); fb(now,1);
      a[b[now],c[now]]:='P';
      dfs(now+1,del);
      a[b[now],c[now]]:='Q';
      fr(now,-1); fb(now,-1);
     end;
   'R':if br(now) and(f[b[now],c[now]]<=0) then
    begin
     fr(now,1);
     a[b[now],c[now]]:='P';
     dfs(now+1,del);
     a[b[now],c[now]]:='R';
     fr(now,-1);
    end;
   'B':if bb(now) and(f[b[now],c[now]]<=0) then
    begin
     fb(now,1);
     a[b[now],c[now]]:='P';
     dfs(now+1,del);
     a[b[now],c[now]]:='B';
     fb(now,-1);
    end;
   'N':if bn(now) and(f[b[now],c[now]]<=0) then
    begin
     fn(now,1);
     a[b[now],c[now]]:='P';
     dfs(now+1,del);
     a[b[now],c[now]]:='N';
     fn(now,-1);
    end;
  end;
 end;

begin
 repeat
  scanf;
  fillchar(f,sizeof(f),0);
  ans:=tot+1;
  dfs(1,0);
  writeln('Minimum Number of Pieces to be removed: ',ans);
 until seekeof;
end.