简单插头 DP 题。
骨牌覆盖，一张骨牌可以看做两个插头相接，即一条跨两格的线。
然后大力分类讨论即可。
这题要求枚举每个格子为障碍物的方案数，考虑正着反着各做一遍，然后统计相同状态之和。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
using namespace std;
const int N = 17;
const int mod = 1e9 + 7;
int n,m,full,a[N + 5][N + 5];
int f[N + 5][N + 5][(1 << N + 1) + 5],g[N + 5][N + 5][(1 << N + 1) + 5];
int ans[N + 5][N + 5];
inline void trans(int &s,int v)
{
s = (s + v) % mod;
}
int main()
{
scanf("%d%d",&n,&m),full = (1 << m + 1) - 1;
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= m;++j)
scanf("%d",a[i] + j),a[i][j] ^= 1;
f[0][m][0] = 1;
for(register int i = 1;i <= n;++i)
{
for(register int j = 0;j < (1 << m);++j)
f[i][0][j << 1] = f[i - 1][m][j];
for(register int j = 1;j <= m;++j)
for(register int s = 0;s <= full;++s)
if(f[i][j - 1][s])
{
int up = (s >> j) & 1,left = (s >> j - 1) & 1;
int v = f[i][j - 1][s];
if(!a[i][j])
!up && !left && (trans(f[i][j][s],v),1);
else if(!up && !left)
trans(f[i][j][s],v),
a[i + 1][j] && (trans(f[i][j][s + (1 << j - 1)],v),1),
a[i][j + 1] && (trans(f[i][j][s + (1 << j)],v),1);
else if(up && !left)
trans(f[i][j][s - (1 << j)],v);
else if(!up && left)
trans(f[i][j][s - (1 << j - 1)],v);
}
}
g[n + 1][1][0] = 1;
for(register int i = n;i;--i)
{
for(register int j = 0;j < (1 << m);++j)
g[i][m + 1][j] = g[i + 1][1][j << 1];
for(register int j = m;j;--j)
for(register int s = 0;s <= full;++s)
if(g[i][j + 1][s])
{
int up = (s >> j - 1) & 1,left = (s >> j) & 1;
int v = g[i][j + 1][s];
if(!a[i][j])
!up && !left && (trans(g[i][j][s],v),1);
else if(!up && !left)
trans(g[i][j][s],v),
a[i][j - 1] && (trans(g[i][j][s + (1 << j - 1)],v),1),
a[i - 1][j] && (trans(g[i][j][s + (1 << j)],v),1);
else if(up && !left)
trans(g[i][j][s - (1 << j - 1)],v);
else if(!up && left)
trans(g[i][j][s - (1 << j)],v);
}
}
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= m;++j)
{
if(a[i][j])
for(register int s = 0;s <= full;++s)
if(!(s & (1 << j - 1)) && !(s & (1 << j)))
ans[i][j] = (ans[i][j] + (long long)f[i][j - 1][s] * g[i][j + 1][s]) % mod;
printf("%d%c",ans[i][j]," \n"[j == m]);
}
}