【CJOJ2499】【DP合集】棋盘 chess

Description

给出一张 n × n 的棋盘，格子有黑有白。现在要在棋盘上放棋子，要求：

• 黑格子上不能有棋子

• 每行每列至多只有一枚棋子

你的任务是求出有多少种合法的摆放方案。答案模 109+7109+7 。

Input

输入的第一行一个整数 n ( n ≤ 15) 。

接下来一个 n × n 的棋盘( 1 表示黑；0 表示白)。

Output

输出一行一个整数，表示合法方案数对 109+7109+7 取模后的结果。

Sample Input

12

000010000000

000000000000

000010011000

001000011011

011000100111

000010110000

101000010001

000001000000

110000000000

000000000010

010010110100

011010010100

Sample Output

349847765

题解

考虑N的范围小于15

可以采用状态压缩

设f[i][j]表示当前第i行，状态为j的方案数

很容易就能够推出转移方程：

f[i][j]=sum(f[i][j-(1<< k)])+f[i-1][j]

其中k满足g[i][j]非黑格子，并且j&(1<<k)不为0

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define MOD 1000000007

inline int read()//只需要读入0或1

{

	  register char ch=getchar();

	  while(ch<'0'||ch>'9')ch=getchar();

	  return ch-48;

}

int N,Ans;

int g[20][20];

int f[20][1<<20];

//f[i][j]表示当前第i行，摆放棋子的情况是j的摆放数

int main()

{

      cin>>N;

      for(int i=1;i<=N;++i)

        for(int j=1;j<=N;++j)

          g[i][j]=read();

      f[0][0]=1;

      for(int i=1;i<=N;++i)//枚举行数

      {

      	   for(int j=0;j<(1<<N);++j)//枚举当前状态

		   {

		   	    f[i][j]=f[i-1][j];//如果当前状态不放棋子，直接由上一状态转移

		        for(int k=0;k<N;++k)//枚举位置

		        {

		        	 if(((1<<k)&j)&&(!g[i][k+1]))//如果当前位置不是黑，并且在状态中放了这个棋子

		        	    f[i][j]=(f[i][j]+f[i-1][j-(1<<k)])%MOD;//状态转移

		        }

		   }

      }

      for(int i=0;i<(1<<N);++i)//统计答案

         Ans=(Ans+f[N][i])%MOD;

      printf("%d\n",Ans);

      return 0;

}

秒客网