leetcode-go/poj/2411.mondriaans-dream/main.cc

#include <cstdio>
#include <cstring>

using namespace std;

const int H = 11, W = 11;
const int N = 1 << W;

long long dp[2][N];

int h, w;

void dfs(int i, int j, int curr, int next) {
  if (j == w) {
    dp[i ^ 1][next] += dp[i][curr];
    return;
  }
  int mask = 1 << j;
  if ((mask & curr) > 0) dfs(i, j + 1, curr, next);
  if ((mask & curr) == 0) dfs(i, j + 1, curr, next | mask);
  if (((mask & curr) > 0) && (((mask << 1) & curr) > 0))
    dfs(i, j + 2, curr, (next | mask) | (mask << 1));
}

int main() {
  while (scanf("%d %d", &h, &w) != EOF) {
    if (h == 0 && w == 0) break;
    memset(dp, 0, sizeof(dp));
    dp[0][(1 << w) - 1] = 1;
    int cur = 0;
    for (int i = 0; i < h; i++) {
      memset(dp[cur ^ 1], 0, sizeof(dp[cur ^ 1]));
      for (int j = 0; j < N; j++) {
        if (dp[cur][j] != 0) dfs(cur, 0, j, 0);
      }
      cur ^= 1;
    }
    printf("%lld\n", dp[cur][(1 << w) - 1]);
  }
  return 0;
}