NC219897. 涛酱和策策的游戏again（by良心出题人wzc）
描述
输入描述
输入包含多组测试数据。（每个测试点最多10组）每组数据的第一行包含三个整数n,m,k，分别代表棋盘的长宽，以及棋盘上多少个格子被限制了不可放置。（1<=n,m<=11,0<=k<=n*m）接下来k行，每行两个整数a,b。代表第a行第b列的格子被限制了不可放置。（1<=a<=n,1<=b<=m）当输入的n=0,m=0,k=0表示输入终止，且该组数据无需处理。
输出描述
每组测试数据输出一个整数代表可行的摆放方案数量，每组样例输出占一行。
示例1
输入:
3 3 1 2 2 1 2 0 1 3 0 4 11 0 10 11 0 5 5 3 1 3 2 1 3 2 5 5 3 1 3 2 3 3 1 0 0 0
输出:
2 1 0 51205 3852472573499 0 80
说明:
C++(clang++11) 解法, 执行用时: 10ms, 内存消耗: 1184K, 提交时间: 2021-04-10 11:17:44
#include<iostream>
#include<cstring>
using namespace std;
const int N=13,M=1<<N;
long long dp[N][M];
int num[N];
int n,m,k;
int main()
{
while(scanf("%d %d %d",&n,&m,&k)&&(n+m+k))
{
memset(dp,0,sizeof dp);
memset(num,0,sizeof num);
for(int i=0;i<k;i++)
{
int a,b;
cin>>a>>b;
// a--,b--;
num[a]+=(1<<(b-1));
}
dp[1][num[1]]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<(1<<m);j++)
{
if(i!=1){
int now=0;
for(int ii=0;ii<m;ii++)
if(!(j&(1<<ii))) now+=(1<<ii);
if((now&num[i])==0) dp[i][now+num[i]]=dp[i-1][j];
}
}
for(int ii=1;ii<m;ii++)
for(int j=0;j<(1<<m);j++)
if((j&(1<<ii))==0 && (j&(1<<(ii-1)))==0)
dp[i][j+(1<<ii)+(1<<(ii-1))]+=dp[i][j];
}
cout<<dp[n][(1<<m)-1]<<endl;
}
return 0;
}