POJ-3254-Corn Fields.txt

//POJ - 3254-Corn Fields
#include "stdio.h"
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 100000000;
const int N = 13;
const int M = 13;

int map[M];
int states[1<<(N-2)];
int dp[M][1<<(N-2)];
int top;

bool ok(int i)
{
	if(!(i & i<<1))
		return true;
	return false;
}

void init(int n)
{
	for(int i=0; i<(1<<n); i++)
	{
		if(ok(i))
		states[++top] = i;
	}
}

bool fit(int i, int k)
{
	if(i & k)
		return false;
	return true;
}

int main()
{
	int m, n;
	while(scanf("%d%d", &m, &n) != EOF)
	{
		memset(dp, 0, sizeof(dp));
		top=0;
		
		int num;
		for(int i=1; i<=m; i++)
		{
			map[i]=0;
			for(int j=1; j<=n; j++)
			{
				scanf("%d", &num);
				if(num==0)
					map[i] += 1<<(n-j);
			}
		}
		
		init(n);
		for(int i=1; i<=top; i++)
		{
			if(fit(states[i], map[1]))
				dp[1][i]=1;
		}
		
		for(int i=2; i<=m; i++)
		{
			for(int j=1; j<=top; j++)
			{
				if(!fit(states[j], map[i]))
					continue;
				for(int k=1; k<=top; k++)
				{
					if(!fit(states[k], map[i-1]))
						continue;
					if(states[j]&states[k])
						continue;
					dp[i][j] += dp[i-1][k];
				}
			}
		}
		
		int ans=0;
		for(int i=1; i<=top; i++)
		{
			ans += dp[m][i];
			ans %= MOD;
		}
		printf("%d\n", ans);
	}
	return 0;
}