Submit: 5168 Solved: 3006
[Submit][Status][Discuss]
Description
Put K kings in the N × N chessboard so that they don't attack each other. How many kinds of placement schemes are there. The king can attack it up and down, left and right, and up and left
There are 8 squares near each of the eight directions from left to right.
Input
Only one line, including two numbers N, K (1 < = N < = 9, 0 < = k < = N * N)
Output
Number of options.
Sample Input
3 2
Sample Output
16
HINT
Source
$f[i][j][k] $indicates the first $I $line, the status of the $I $line is $j $, and $k $schemes are put
Enumerate the status of the previous line when transferring
Need to preprocess the number of kings in each state
// luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #define int long long using namespace std; const int MAXN = 10; //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++) char buf[1<<22],*p1=buf,*p2=buf; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int f[MAXN][1<<MAXN][MAXN*MAXN]; int N, K; int times[1<<MAXN],can[1<<MAXN]; int calc(int x) { int num = 0; for(int i = 0;i < N; i++) if( x & (1 << i) ) num++; return num; } main() { #ifdef WIN32 freopen("a.in","r",stdin); #endif //printf("%d %d %d\n",0<<1,0>>1,0); N = read(), K = read(); int Max = (1 << N) - 1; for(int i = 0;i < Max; i++) times[i] = calc(i), can[i] = (i & (i>>1)) == 0 ? 1 : 0; f[0][0][0] = 1; for(int i = 1;i <= N; i++) for(int j = 0;j < Max; j++) if(can[j]) for(int k = 0;k < Max; k++) if(((j & k) == 0) && ((j & (k << 1)) == 0) && ((j & (k >> 1)) == 0)) for(int l = times[j]; l <= K; l++) f[i][j][l] += f[i-1][k][l - times[j]]; int ans = 0; for(int i = 0;i <= Max; i++) ans += f[N][i][K]; printf("%lld", ans); return 0; }