题意 给定一个$12*12$的矩阵，每个元素是'.'或'X'。现在要求$1*2$的骨牌铺满整个矩阵，
'X'处不能放置骨牌。求方案数。
这道题其实和 Uva11270 是差不多的，就是加了一些条件。
那么分类讨论的时候情况里面要加点东西：
1、当前格子为'X'，这个时候这个格子上不能放置骨牌，那么状态只能转移到下一位，注意最后一位应该变成$1$
因为这个格子是被填充的。
2、当前格子为'.'，这个时候这个格子上可以往左边横着放骨牌，要求$grid[i][j-1]为'.'$；
也可以往上面放骨牌，要求$grid[i-1][j]为'.'$；
也可以不放。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second typedef long long LL; LL f[2][(1 << 14) + 5];
int n, m;
int x; inline void up(int a, int b){
if (b & (1 << m)) f[x][b ^ (1 << m)] += f[x ^ 1][a];
} class DominoTiling {
public:
long long count(vector<string> grid) {
n = (int)grid.size();
m = (int)grid[0].size();
memset(f, 0, sizeof f);
x = 0;
f[x][(1 << m) - 1] = 1; rep(i, 0, n - 1){
rep(j, 0, m - 1){
x ^= 1;
memset(f[x], 0, sizeof f[x]);
if (grid[i][j] == 'X'){
rep(k, 0, (1 << m) - 1) up(k, (k << 1) ^ 1);
continue;
} rep(k, 0, (1 << m) - 1){
up(k, k << 1);
if (i && !(k & (1 << (m - 1))) && grid[i - 1][j] == '.') up(k, (k << 1) ^ (1 << m) ^ 1);
if (j && !(k & 1) && grid[i][j - 1] == '.') up(k, (k << 1) ^ 3);
}
}
} return f[x][(1 << m) - 1];
}
};