学步园

题意:给出个N*M的矩阵，1可以放，0不可以放，相邻之间不能放，求放的方法数。

思路：最后有bug，还是参考的@ZeroClock大神。。。   

poj 1185炮兵阵地的简化版。

#include<iostream>
#include<cstdio>
#include<cstring>
#define Mod 100000000
using namespace std;
int dp[15][4200];
int map[15][15] , h[15] , acc[4200];
int n , m , top;
void init() {
    int i , j , state;
    for(i = 0 ; i < n ; i ++) {
        state = 0;
        for(j = 0 ; j < m ; j ++) {
            state = state << 1;
            if(map[i][j]==1) state += 1;    
        }
        h[i] = state;
    }
    top = 0;
    for(j = 0 ; j <(1<<m) ; j ++) {
        if(j&(j<<1)) continue;
        acc[top++] = j;
    }
}
int main() {
    int i , j , k;
    int k1 , k2;
    while(~scanf("%d%d",&n,&m)) {
        for(i = 0 ; i < n ; i ++)
            for(j = 0 ; j < m ; j ++)
            scanf("%d",&map[i][j]);
            init();
            memset(dp , 0 , sizeof(dp));
            for(j = 0 ; j < top ; j ++) {
                k = acc[j];
                if((k & h[0]) == k) {
                    dp[0][k] = 1;
                    //printf("运行 %d\n",k);
                }  
            }
            int sum;
            for(i = 1 ; i < n ; i ++) {
                for(j = 0 ; j < top ; j ++) {
                    k1 = acc[j];
                    if((k1 & h[i])==k1) {
                        sum = 0;
                        for(k = 0 ; k < (1<<m) ; k ++) {
                            if(!(k & k1)) sum += dp[i-1][k]%Mod;
                        }
                        dp[i][k1] = sum; 
                    }
                }
            }
            int cnt = 0;
            for(j = 0 ; j <(1<<m) ; j ++)
            cnt += dp[n-1][j]%Mod;
            printf("%d\n",cnt%Mod);
    }    
}