Problem Specification Value
Time Limit 10 Sec
Memory Limit 162 MB
Submit 2697
Solved 1588

Description

在 N×N 的棋盘里面放 K 个国王, 使他们互不攻击, 共有多少种摆放方案. 国王能攻击到它上下左右, 以及左上左下右上右下八个方向上附近的各一个格子, 共 8 个格子.

Input

只有一行, 包含两个数 N, K (1 <=N <=9, 0 <=K <=N * N)

Output

方案数.

Sample Input

3 2

Sample Output

16

HINT

Source

状压 DP, 将每一个列存上所有国王的位置, true or false, 然后推断下一行, 注意不要溢出.

话说把这个写成 class 实在是太累......


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 10, maxm = 90, maxk = 512;

int n, K;
lli dp[maxn][maxm][maxk];
bool dp_ok[maxk][maxk], dp_ok_2d[maxk];

#define states(__x) (1 << (__x))
#define get_pos(__st, __dig) (((__st) >> ((__dig) - 1)) & 1)
int get_digs(int __st) { int res=0;for(int i=1;i<=16;i++)res+=(int)(get_pos(__st,i));return res; }

// This function preprocesses the required dp data.
// dp_ok[x][y] Whether state x is safe as a previous row for state y.
void preprocess_dp(void)
{
    // Current row is of state i.
    for (int i = 0; i < states(n); i++) {
        // Whether this is safe for itself, i.e. do not contradict adjacence
        // by itself on the same row.
        bool ok = true;
        for (int j = 2; j <= n; j++)
            if (get_pos(i, j) && get_pos(i, j - 1))
                ok = false;
        dp_ok_2d[i] = ok; // Whether this is legal on this position
        if (!ok)
            continue;
        // Previous row is of state j.
        for (int j = 0; j <= i; j++) {
            bool res = true;
            for (int k = 1; k <= n; k++)
                if (get_pos(i, k)) {
                    // Avoid segmentation violation
                    if (k > 1 && get_pos(j, k - 1)) res = false;
                    if (get_pos(j, k)) res = false;
                    if (k < n && get_pos(j, k + 1)) res = false;
                }
            dp_ok[i][j] = dp_ok[j][i] = res;
        }
    }
    return ;
}

int main(int argc, char** argv)
{
    // dp[i][j][k]: row #i, placed j kings, status of all columns = bin(k)
    scanf("%d%d", &n, &K);
    // Preprocess dp availability
    preprocess_dp();
    // Setting default data
    dp[0][0][0] = 1;
    // Iterating on row #i
    for (int i = 1; i <= n; i++)
        // Row #i has state j
        for (int j = 0; j < states(n); j++) {
            if (!dp_ok_2d[j]) // Inlegitimate even on this position
                continue;
            int c_kings = get_digs(j);
            // If row #i-1 has state k
            for (int k = 0; k < states(n); k++) {
                if (!dp_ok_2d[k])
                    continue;
                if (!dp_ok[j][k])
                    continue;
                int o_kings = get_digs(k);
                // printf("%d %d %d | %d %d\n", i, j, k, c_kings, o_kings); // Debug only
                for (int l = c_kings + o_kings; l <= K; l++)
                    dp[i][l][j] += dp[i - 1][l - c_kings][k];
            }
        }
    lli res = 0;
    for (int i = 0; i < states(n); i++)
        res += dp[n][K][i];
    printf("%lld\n", res);
    return 0;
}