德玛西亚万岁

状压dp
第一次写状压dp的题目，可能是因为这种类型的比较难吧，所以是第一次做到。
题解：
我们可以用二进制来描述方格，1表示有德玛西亚，0表示没有。
样例1中第一行的三个方格都可以站人
一共有五种情况分别是

第一行的五种情况
第一种    000
第二种    001
第三种    010
第四种    100
第五种    101

再看第二行

第二行情况
第一种    000
第二种    010
第三种    001

第二行的第一种情况是有5种方法的，第二种情况是有4种方法（与第一行第三种情况冲突），第三种情况是有3种方法（与第一行第2、5钟情况冲突）

第三行情况

第一种    000
第二种    100

第三行的第一种情况可以完美兼容第二行所有情况，所以一共是5+4+3=12钟情况
第三行的第二种情况也是可以完美兼容第二行的所有情况（没有冲突就视为可以），所以一共是5+4+3=12种情况
综上所述，总共的情况就是24种。
所以我们先把每一行能放东西的格子用二进制表示出来。
再枚举这个长度所有的二进制状态（表示每种占位）并且将可行的占位记录下来
要判断是否与上面一行冲突和与左右两边冲突是否与地图样貌冲突

if(((j&lines[i])!=j)||(j&(j>>1))) continue;  //判断是否与地图匹配/是否左右相邻
if(k&j) continue;                            //判断是否与上层冲突

代码：

#pragma GCC optimize(3,"Ofast","inline")
#include 
const int maxn = 15;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
int dp[maxn][1<<maxn];
int lines[maxn];
int main()
{
    int n,m,x;
    while(cin>>n>>m){
        memset(lines,0,sizeof(lines));
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<m;j++){
                scanf("%d",&x);
                lines[i]|=(x<<j);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<(1<<m);j++){
                if(((j&lines[i])!=j)||(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;
                }
            }
        }
        ll ans=0;
        for(int i=0;i<(1<<m);i++){
            ans=(ans+dp[n][i])%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}