国王（C++）

【问题描述】

在n×n (1<=n<=10)的棋盘上放k(0<=k<=n×n)个国王（一个国王可以攻击相邻的8个格子），求使他们无法互相攻击的方案总数。

【输入格式】

只有一行为两个整数n和k。

【输出格式】

输出一行表示方案总数，若不能够放置则输出0。

【输入样例1】

3 2

【输出样例1】

16

【输入样例2】

4 4

【输出样例2】

79
 

#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 10;
const int MAX_STATE = 1 << MAX_N;
long long f[MAX_N + 1][MAX_STATE][MAX_N * MAX_N + 1];

int main() {
    int n, k;
    cin >> n >> k;

    f[0][0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < (1 << n); ++j) {
            for (int l = 0; l <= k; ++l) {

                if (f[i-1][j][l] == 0) continue;

                int p = __builtin_popcount(j);


                for (int c = 0; c < (1 << n); ++c) {
                    if (c & (c >> 1)) continue;
                    int curr_k = __builtin_popcount(c);

                    bool valid = true;
                    for (int col = 0; col < n; ++col) {
                        if (c & (1 << col)) {
       
                            if (col > 0 && (j & (1 << (col - 1)))) valid = false;
    
                            if (j & (1 << col)) valid = false;

                            if (col < n - 1 && (j & (1 << (col + 1)))) valid = false;
                        }
                    }

                    if (!valid) continue;

                    f[i][c][l + curr_k] += f[i-1][j][l];
                }
            }
        }
    }

    long long result = 0;
    for (int state = 0; state < (1 << n); ++state) {
        result += f[n][state][k];
    }

    cout << result << endl;
    return 0;
}