POJ 2411 Mondriaan's Dream by iloahz@Attiix

pku2411.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 12;
const int MAXS = 2048;

int h, w;
long long f[2][MAXS];

long long dp(int m, int n){
    int s = 1 << m;
    int l = 0, r = 1;
    memset(f, 0, sizeof(f));
    f[l][0] = 1;
    for (int i = 0;i < n;i++){
        for (int j = 0;j < s;j++) f[r][j] = 0;
        for (int j = 0;j < s;j++){
            if (f[l][j]){
                for (int k = 0;k < s;k++){
                    if ((k & j) == 0){
                        int x = j | k;
                        for (int p = 3;p < s;p <<= 1)
                            if ((x & p) == 0) x |= p;
                        if (x + 1 == s) f[r][k] += f[l][j];
                    }
                }
            }
        }
        l ^= 1;
        r ^= 1;
    }
    return f[l][0];
}

int main(){
#ifdef  ATTIIX
    freopen("pku2411.in", "r", stdin);
#endif
    while (~scanf("%d%d", &h, &w) && (h > 0)){
        printf("%lld\n", dp(h, w));
    }
    return 0;
}