先标记所有可行方案再从可行方案中寻找可转移的状态

最后进行转移
代码code——————————————————————————

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N=14,M=1<<12,mod=1e8;

#define ll long long

int n,m;
int map[N];
ll f[N][M];
vector<int> state;
vector<int> tran[M];

bool check(int state){return !(state&state>>1);}

void solve()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
        {
            int t;cin>>t;
            map[i]|=!t<<j;
        }
    for(int i=0;i<(1<<m);i++)
        if(check(i))
            state.push_back(i);

    for(int pre_st:state)
        for(int next_st:state)
            if((pre_st&next_st)==0)
                tran[pre_st].push_back(next_st);

    f[0][0]=1;

    for(int i=1;i<=n+1;i++)
        for(int a:state)
            for(int b:tran[a])
            {
                if((a&map[i])!=0) break;
                f[i][a]=(f[i][a]+f[i-1][b])%mod;
            }
    ll res=0;
    for(auto i:state) res+=f[n][i];
    cout<<res%mod;
}
int main()
{
    solve();
}