牛客——德玛西亚万岁（状压DP）

原题链接

题意：

已知一个n*m的01矩阵，0表示这个格子不可以站人，1表示这个格子可以站人。规定上下左右相邻的格子不能站人，问有多少种站人的方法。

思路：

因为n,m都很小，而且能够站人的人数也不是固定的。考虑状压枚举每一行的状态，进行转移。

在枚举状态的时候，有三种状态是不合法的。

1.当前的状态与地图的状态相矛盾；

2.当前状态本身不合法，即存在左右相邻的情况；

3.当前状态无法由上一个状态转移而来，即存在上下相邻的情况。

最后统计输出即可。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
#define I_int ll
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    cout<<endl;
}

const int maxn=15,mod=100000000;
int n,m;
int dp[maxn][1<<16];///dp[i][j]表示第i行状态为j的方案数
int mp[maxn];///mp[i]表示第i行的地图状态

int main(){
    while(~scanf("%d%d",&n,&m)){
        memset(mp,0,sizeof mp);///初始化
        memset(dp,0,sizeof dp);///初始化
        dp[0][0]=1;///什么也不放，只有一种方案
        for(int i=1;i<=n;i++)
            for(int j=0;j<m;j++){
                int x;scanf("%d",&x);
                mp[i]|=(x<<j);
            }
        for(int i=1;i<=n;i++)///枚举当前在哪一行
            for(int j=0;j<(1<<m);j++){///枚举当前这一行的状态
                if((j&mp[i])!=j) continue;///当前这行的状态与地图的状态不符合
                if(j&(j>>1)) continue;///左右有相邻的
                for(int k=0;k<(1<<m);k++){///枚举上一行的状态
                    if(k&j) continue;///上下有相邻的
                    dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;///合法情况，可以由上一行的状态k转移过来
                }
            }
        int res=0;
        ///统计并且输出答案
        for(int i=0;i<(1<<m);i++)
            res=(res+dp[n][i])%mod;
        printf("%d\n",res);
    }
    return 0;
}