没什么可说的，入门级状压DP。直接撸掉

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

#include <map>

#include <queue>

#include <stack>

#include <set>

#define LL long long

#define FOR(i, x, y) for(int i=x;i<=y;i++)

using namespace std;

const int maxn = 5000;

const int MOD = 100000000;

int N, M, K;

int C[20], state[maxn];

int dp[20][maxn];

bool judge(int x)

{

    if(x & (x << 1)) return false;

    return true;

}

void init()

{

    memset(dp, 0, sizeof(dp));

    memset(state, 0, sizeof(state));

    memset(C, 0, sizeof(C));

    int r = (1 << M) - 1; K = 0;

    FOR(i, 0, r) if(judge(i)) state[++K] = i;

}

int main()

{

    while(scanf("%d %d", &N, &M)!=EOF)

    {

        init();

        int X;

        FOR(i, 1, N)

        FOR(j, 1, M)

        {

            scanf("%d", &X);

            if(X == 0) C[i] = C[i] | (1 << (M - j));

        }

        FOR(i, 1, K)

        {

            if(!(state[i] & C[1])) dp[1][i] = 1;

        }

        FOR(i, 2, N)

        FOR(j, 1, K)

        {

            if(C[i-1] & state[j]) continue;

            FOR(l, 1, K)

            {

                if((C[i] & state[l]) || (state[l] & state[j])) continue;

                dp[i][l] = (dp[i-1][j] + dp[i][l]) % MOD;

            }

        }

        int ans = 0;

        FOR(i, 1, K) ans = (ans + dp[N][i]) % MOD;

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

    }

    return 0;

}