Hardwood Floor

题目描述

The banquet hall of Computer Scientists’ Palace has a rectangular form of the size $M \times N$. It is necessary to lay hardwood floors in the hall. There are wood pieces of two forms:

• rectangles ($2 \times 1$)
• corners (squares $2 \times 2$ without one $1 \times 1$ square)

You have to determine $X$ - the number of ways to cover the banquet hall.

Remarks. The number of pieces is large enough. It is not allowed to leave empty places, or to cover any part of a surface twice, or to saw pieces.

题意概述

有一个$M \times N$的网格，要求用两种方块覆盖它，一种是$2 \times 1$的方块，一种是$2 \times 2$挖去$1 \times 1$的方块。方块可以旋转。求方案数。

数据范围：$1 \le M, N \le 9$。

算法分析

用$f_{i, j}$表示前$(i-1)$行都已填满且第$i$行的状态为$j$的方案数，转移时枚举$j$可以转移到的状态。暴力计算即可发现合法的转移不会太多。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 11;
  int n, m, f[N][1 << N];
  void input() { io > n > m; }
  void update(int x, int y, int s, int val, int p) {
    if (y == (1 << m) - 1) { f[x][s] += val; return; }
    for (int i = p; i < m; ++ i)
      if (! (y & 1 << i)) {
        if (! (s & 1 << i)) {
          update(x, y | 1 << i, s | 1 << i, val, i + 1);
          if (i && ! (s & 1 << i - 1)) update(x, y | 1 << i, s | 1 << i | 1 << i - 1, val, i + 1);
          if (i < m - 1 && ! (s & 1 << i + 1)) update(x, y | 1 << i, s | 1 << i | 1 << i + 1, val, i + 1);
        }
        if (i < m - 1 && ! (y & 1 << i + 1)) {
          update(x, y | 1 << i | 1 << i + 1, s, val, i + 2);
          if (! (s & 1 << i)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i, val, i + 2);
          if (! (s & 1 << i + 1)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i + 1, val, i + 2);
        }
      }
  }
  void process() {
    f[0][(1 << m) - 1] = 1;
    for (int i = 0; i <= n; ++ i)
      for (int j = 0; j < 1 << m; ++ j)
        if (f[i][j]) update(i + 1, j, 0, f[i][j], 0);
    io < f[n + 1][0] < '\n';
  }

public:
  void solve() { input(), process(); }
} solver;

signed main() {
  solver.solve();
  return 0;
}