291 蒙德里安的梦想

f[i][j]表示第i列有来自上一列的j（用二进制表示有几行就有几位，1表示突起，0表示没有突起）的突起时有几种摆放方式
在确定几行几列的图之后，先预处理st数组，这个数组是确定每一列可以怎么放（不能有奇数个连续的0）
比如在n=4的时候 有十五个状态
st[0] = 1, st[1] = 0, st[2] = 0, st[3] = 1, st[4] = 0, st[5] = 0, st[6] = 0, st[7] = 0, st[8] = 0, st[9] = 1, st[10] = 0, st[11] = 0, st[12] = 1,
st[13] = 0, st[14] = 0, st[14=5] = 1,
只有 0:(0000)₂
        3:(0011)₂
        9:(1001)₂
        12:(1100)₂
        15:(1111)₂
表示当前这一列可以有这几种放的方式（1表示突出，0表示不突出）
预处理结束之后
先将f[0][0]置为1因为这表示第零列没有突出只有一种摆放方式
然后开始遍历m列，每一列(2ⁿ-1)需要遍历
上一列的突出与这一列的突出没有冲突并且st[j|k](也就是两个突起与起来还符合st规则）就算一种方法

#include<bits/stdc++.h>
using namespace std;

const int N = 12, M = 1 << N;

int n, m; // n是列
long long f[N][M]; //   N是列 M用二进制表示所以需要往左移N位每一位表示当前这一行有没有突出
bool st[M]; 

int main() {
    while( cin >> n >> m, n || m) {
        
        memset(f, 0, sizeof f);
        //预处理st 表示那些情况是可以的
        for (int i = 0; i < 1 << n; i++) {
            st[i] = true;
            int cnt = 0;   //表示当前连续零的个数

            for (int j = 0; j < n; j ++) {
                if (i >> j & 1) {  // 如果当前这一位是一
                    if (cnt & 1) {
                        st[i] = false;   //cnt & 1 如果cnt是奇数那么这个与就是一 如果cnt是偶数这个与就是零
                        break;                        
                    }
                }
                else cnt ++ ;
            }
            
            if (cnt & 1) st[i] = false;  //如果最后一位是奇数也置为false
        }
        f[0][0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < 1 << n; j++) {
                for (int k = 0; k < 1 << n; k++) {
                    if ((j & k) == 0 && st[j|k]) f[i][j] += f[i - 1][k];
                }
            }
        }
        cout << f[m][0] << endl;
    }
}