德玛西亚万岁 题解

二进制状压dp，只要相邻行列没有同时有两个战士，并且满足只有1的位置有战士，即可。
注意多组数据要重置f数组

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=100000000;
int st[1<<12];
int mp[14][14];
int mpst[14];
int f[14][1<<12];
bool judge(int x)
{
    while(x)
    {
        if((x&1)&&(x&2)) return false;
        x>>=1;
    }
    return true;
}
signed main()
{
    int n,m;
    while(~scanf("%lld%lld",&n,&m))
    {
        memset(f,0,sizeof(f));
        memset(mpst,0,sizeof(mpst));
        int id=0;
        for(int i=0;i<(1<<m);i++)
        {
            if(judge(i)) st[++id]=i;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%lld",&mp[i][j]);
                mpst[i]=(mpst[i]<<1)+(mp[i][j]==1);
            }
        }
        //把地图的每一行表示成状态
        //如果状态和st数组中状态取按位或结果不等于地图状态
        //说明st数组中的状态在这一行不合法 无法进行转移
        //这一行跟上一行的状态取按位与 如果不为0
        //说明新的状态与上一行状态矛盾 不可取
        for(int j=1;j<=id;j++)
        {
            if((st[j]|mpst[1])!=mpst[1]) continue;
            f[1][j]=1;
        }
        for(int i=2;i<=n;i++)//从第一行开始递推
        {
            for(int j=1;j<=id;j++)//枚举可能的方案
            {
                if((st[j]|mpst[i])!=mpst[i]) continue;
                for(int k=1;k<=id;k++)
                {
                    if(st[j]&st[k]) continue;
                    if((st[k]|mpst[i-1])!=mpst[i-1]) continue;
                    f[i][j]=(f[i][j]+f[i-1][k])%mod;
                }
            }
        }
        int ans=0;
        for(int j=1;j<=id;j++)
        {
            ans=(ans+f[n][j])%mod;
        }
        printf("%lld\n",ans);
    }
}