bzoj 1087[SCOI 2005]相互不可侵King


Description
N×Nの碁盤の中にK人の王が入っていて、お互いに攻撃しないようにして、何種類の配置案がありますか.王は上下左右、左上左下右上右下8方向の各格子、計8個の格子を攻撃することができる.
Input
2個の数N,K(1<=N<=9,0<=K<=N*N)を含む1行のみ
Output
シナリオ数.
Sample Input
3 2
Sample Output
16
var n,m,t,i,j,k,x:longint;
ans:int64;
p:boolean;
a:array[1..1024]of longint;
s:array[1..1024]of string;
w:array[1..1024,1..1024]of longint;
f:array[1..10,1..1024,0..100]of int64;
procedure wwj(x,y:longint;c:string);
begin
  if x>n then
  begin
    inc(t);
    s[t]:=c;
    a[t]:=y;
    exit;
  end;
  wwj(x+1,y,c+'0');
  if c[x-1]<>'1' then wwj(x+1,y+1,c+'1');
end;
begin
  ans:=0;
  fillchar(f,sizeof(f),0);
  readln(n,m);
  wwj(1,0,'');
  for i:=1 to t do
  s[i]:='0'+s[i]+'0';
  for i:=1 to t do
  for j:=1 to t do
  begin
    p:=true;
    for k:=2 to n+1 do
    begin
      if s[i][k]='1' then
      if(s[j][k-1]='1')or(s[j][k+1]='1')or(s[j][k]='1') then p:=false;
      if s[j][k]='1' then
      if(s[i][k-1]='1')or(s[i][k+1]='1')or(s[i][k]='1') then p:=false;
    end;
    if p then w[i,j]:=0 else w[i,j]:=1;
  end;
  for i:=1 to t do f[1,i,a[i]]:=1;
  for i:=2 to n do
  for j:=1 to t do
  for k:=1 to t do
  if w[j,k]=0 then
  for x:=a[k] to m do
  f[i,k,x]:=f[i,k,x]+f[i-1,j,x-a[k]];
  for i:=1 to t do ans:=ans+f[n,i,m];
  write(ans);
end.