bzoj 1087[SCOI 2005]相互不可侵King
1451 ワード
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
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.