学步园

状态压缩dp

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define mod 100000000
int n,m;
int map[15];
int dp[15][1<<12];
int s[1<<12],cnt;
bool judge(int x)
{
	if((x<<1)&x)
		return 0;
	return 1;	
}
void init()
{
	cnt=0;
	for(int i=0;i<(1<<m);i++)
		if(judge(i))
		{
			s[cnt]=i;
			cnt++;
		}
}
int main()
{
	while(cin>>n>>m)
	{
		memset(map,0,sizeof(map));
		memset(dp,0,sizeof(dp));
		init();
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				int tmp;
				scanf("%d",&tmp);
				if(tmp==0)
					map[i]|=1<<j;
			}
		for(int i=0;i<cnt;i++)	
		{
			if(map[0]&s[i])continue;
			dp[0][i]=1;
		}	
			
		for(int r=1;r<n;r++)
		{
			for(int i=0;i<cnt;i++)
			{
				if(map[r]&s[i]) continue;
				for(int j=0;j<cnt;j++)
				{
					if(s[i]&s[j]) continue;
					dp[r][i]+=dp[r-1][j];
				}
			}
		}
		int ans=0;
		for(int i=0;i<cnt;i++)
			ans=(ans+dp[n-1][i])%mod;
		cout<<ans<<endl;
	}
	return 0;
}