学步园

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 100000000;
int n, m, M;
int state[400], tot;
int a[15];
bool f[400][400];
int dp[13][400];
void add(int &a, int b) {
	a += b;
	if(a >= mod) a -= mod;
}
void init() {
	tot = 0;
	M = (1<<m);
	int i, j;
	for(i = 0; i < M; i++) {
		if(i&(i<<1)) continue;
		state[tot++] = i;
	}
	for(i = 0; i < tot; i++)
		for(j = 0; j < tot; j++)
			f[i][j] = !(state[i]&state[j]);
}
int main() {
	int x, i, j, k;
	while(~scanf("%d%d", &n, &m)) {
		init();
		memset(a, 0, sizeof(a));
		for(i = 0; i < n; i++)
			for(j = 0; j < m; j++) {
				scanf("%d", &x);
				if(!x)a[i] |= (1<<j);
			}
		memset(dp, 0, sizeof(dp));
        for(i = 0; i < tot; i++) if(!(a[0] & state[i]))
            dp[0][i] = 1;
		for(i = 1; i < n; i++)
			for(j = 0; j < tot; j++) if(dp[i-1][j])
                for(k = 0; k < tot; k++) if(f[j][k] && !(a[i]&state[k]))
                    add(dp[i][k], dp[i-1][j]);
		int ans = 0;
		for(i = 0; i < tot; i++) if( dp[n-1][i])
            add(ans, dp[n-1][i]);
		printf("%d\n", ans);
	}
	return 0;
}