特殊方格棋盘【状压】

特殊方格棋盘

题目描述

在 n * n (n (leq) 20) 的方格棋盘上放置n 个车，某些格子不能放，求使它们不能互相攻击的方案总数。

注意：同一行或同一列只能有一个车，否则会相互攻击

输入

输入文件第一行，有两个数n, m ,n表示方格棋盘大小,m表示不能放的格子数量

下面有m行,每行两个整数,为不能放的格子的位置。

输出

输出文件也只有一行，即得出的方案总数。

Sample

2 1
1 1

1

分析

显然每一行或每一列只能放一个车，否则会相互攻击。

我们用 1 表示放车，0 表示不放，dp[ i ]表示达到状态 i 时的方案数

假如某一行的状态为 1 0 0 1 1

达到这个状态的方案数应该是达到状态0 0 0 1 1，1 0 0 0 1，1 0 0 1 0的方案数之和。

我们可以通过lowbit枚举状态 i 的每一位 1。则 dp[i] += dp[i & ~lowbit(j)];

还用我们上面的栗子吧

第一次取lowbit，得到 0 0 0 0 1

​ 取反，得到 1 1 1 1 0

​ & i，得到 1 0 0 1 0

第二次取lowbit，第三次取lowbit同理。最终得到的正好我们做状态转移需要的前面的一个状态

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
ll dp[1<<20], map[25];//map记录每行不能放的地方
int n, m;
int lowbit(int x){return x & -x;}
int main(){
    scanf("%d%d", &n ,&m);
    for(int i=1; i<=m; i++){
        int a, b; scanf("%d%d", &a, &b);
        map[a] += 1<<(b-1);//记录第a行不能放的地方
    }
    dp[0] = 1;//达到状态0只有一种方案
    for(int i=1; i<(1<<n); i++){
        int tot = 0;//记录状态中包含的1个数
        for(int j=i; j; j-=lowbit(j)) tot++;//枚举最低位1
        for(int j=i; j; j-=lowbit(j)){//枚举转移给当前状态的以前的状态
            if(!(map[tot] & lowbit(j))) dp[i] += dp[i & ~lowbit(j)];//不能在不能放的地方放
        }
    }
    printf("%lld
", dp[(1<<n)-1]);//最终的答案是从1到n各位都为1的状态的方案数
    return 0;
}