SGU 131 Hardwood floor by iloahz@Attiix

sgu131.cpp

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

using namespace std;

const int MAXN = 11;
const int MAXS = 1 << 9;
const int d[][2] = {{1, 1}, {3, 0}, {1, 3}, {2, 3}, {3, 1}, {3, 2}};

int m, n, s;
__int64 f[2][MAXS];
int l, r;

void init(){
    scanf("%d%d", &m, &n);
}

void dfs(int a, int b, int i, int j){
    if ((a ^ s) < (1 << i) - 1) return;
    if (i >= n){
        f[r][b ^ s] += f[l][j];
        return;
    }
    if (((1 << i) & a)) dfs(a, b, i + 1, j);
    for (int k = 0;k < 6;k++){
        int x = d[k][0] << i;
        int y = d[k][1] << i;
        if ((a & x) == 0 && (b & y) == 0) dfs(a | x, b | y, i + 1, j);
    }
}

void dp(){
    s = 1 << n;
    l = 0;
    r = 1;
    memset(f, 0, sizeof(f));
    f[l][0] = 1;
    for (int i = 0;i < m;i++){
        for (int j = 0;j < s;j++) f[r][j] = 0;
        for (int j = 0;j < s;j++){
            if (f[l][j]) dfs(j | s, s, 0, j);
        }
        l ^= 1;
        r ^= 1;
    }
    printf("%I64d\n", f[l][0]);
}

int main(){
#ifdef  ATTIIX
    freopen("sgu131.in", "r", stdin);
#endif
    init();
    dp();
    return 0;
}