Description
在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。
Input
只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)
Output
方案数。
Sample Input
3 2
Sample Output
16
HINT
状压DP。
定义dp[i][j][k]代表到第i行,当前行为j,已经放了k个国王的方案数。
则状态转移方程:
dp[i][b][j+get(b)]+=dp[i-1][a][j];
其中a和b必须合法,j为第i-1行及以前放的国王数,get(b)是取b的二进制中1的个数,表示增加的国王数。
注意不要取(1<<0)位,特判要判掉,因为不合法。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL dp[12][1245][90];
int n,m;
int get(int x)
{
int ans=0;
for(int i=n;i>=1;i--)
{
if(x&(1<<i)) ans++;
}
return ans;
}
bool check(int a)
{
return (a&(a<<1)) && (a&(a>>1));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=(1<<(n+1))-1;i++) dp[1][i][get(i)]=1;
for(int i=2;i<=n;i++)//行
{
for(int a=0;a<=(1<<(n+1))-1;a++)//从a转移
{
for(int b=0;b<=(1<<(n+1))-1;b++)//到b
{
if( !(a&1) && !(b&1) && !(a&(b>>1)) && !(a&b) && !(a&(b<<1)) && !check(a) && !check(b) )
for(int j=0;j<=m-get(b);j++)
{
dp[i][b][j+get(b)]+=dp[i-1][a][j];
}
}
}
}
LL ans=0;
for(int i=0;i<=(1<<(n+1))-1;i++)
ans+=dp[n][i][m];
printf("%lld",ans);
return 0;
}