Guards In The Storehouse | Codeforces 845F
给定一个 \(n \times m\) 的网格，有些位置是障碍，其他是空地。
在一个空地放灯可以照亮这个灯向右，向下第一个障碍前的所有方格。
求有多少种在空地上放灯的方案，使得最多 \(1\) 个空地没有被照亮，对 \(10^9+7\) 取模。
\(nm \le 250\)
\(\land\) 是逻辑与，\(\lor\) 是逻辑或。
首先 \(nm \le 250 \Rightarrow \min\{n,m\} \le 15\)。
如果 \(n < m\)，就可以将行列转置，问题不变，但 \(m \le 15\) 了。
容易想到对每一行状压，状压一行中每个格子向上第一个障碍前是否有灯（即这个格子是否有向下的光）。
这样时间复杂度过高，感觉行不通，于是考虑压轮廓线，按照从上到下，从左到右的顺序放灯。
设 \(f_{i\,a,b,S}\) 表示目前将要决定格子 \(i=(x,y)\) 放不放灯，\(a\) 表示从 \(i\) 向左第一个障碍前是（\(1\)）否（\(0\)）有灯（即 \(i\) 左边是否有向右的光），\(b\) 表示有几个目前已决定有没有放灯的空地没有被照亮，而 \(S\) 是压的是第 \(x\) 行前 \(y-1\) 个格子和第 \(x-1\) 行后 \(m-y+1\) 个格子上是（\(1\)）否（\(0\)）有向下的光。
图中的情况 \(a = 0, b = 1, S = \{0,0,1,0,1\}\)。
转移就三种情况（先不考虑从一行最后一个格子转移到下一行第一个格子的情况）：
- 格子 \(i\) 是障碍，那么它会挡住向右和向下的光，形式化地： \[
a \rightarrow 0,S \rightarrow S \setminus \{y\}\\\\
\]
转移到 ```f[nxt][0][b][~(~S | 1 << y)]```。 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
- 格子 $i$ 是空地，在格子 $i$ 放灯，那么它会产生向右和向下的光。
$$
a \rightarrow 1,S \rightarrow S \cup \{y\}
$$
```f[i][a][b][S]``` 转移到 ```f[nxt][1][b][S | 1 << y]```
- 格子 $i$ 是空地，不在格子 $i$ 放灯，那么还要考虑 $i$ 会不会被照亮。
如果 $a=1 \lor y \in S$，那么 $i$ 会被照亮，$a,b$ 和 $S$ 都不变，否则 $i$ 不会被照亮， $b$ 必须为 0，转移后变为 $1$，$a$ 和 $S$ 不变。
当 $i$ 是一行最后一个格子时，唯一区别是转移后 $a$ 变为 $0$，因此在代码里无需单独讨论。
答案就是格子 $(n+1,1)$ 的所有 ```f``` 值之和，因为状态的定义是目前**将要**决定这个格子放不放灯。
代码：
```cpp
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
using namespace std;
typedef long long ll;
const ll P = 1e9 + 7;
int n, m, f[255][2][2][1 << 15]; char s[255][255];
int main() {
cin >> n >> m;
For(i, 0, n) scanf("%s", s[i]);
if(n < m) {
For(i, 0, n) For(j, i + 1, m) swap(s[i][j], s[j][i]);
swap(n, m);
}
f[0][0][0][0] = 1;
For(i, 0, n) For(j, 0, m) rep(a, 0, 1) rep(b, 0, 1) For(S, 0, 1 << m) {
int x = f[i * m + j][a][b][S], nxt = i * m + j + 1;
if(!x) continue;
if(s[i][j] == 'x') (f[nxt][0][b][~(~S | 1 << j)] += x) %= P;
else {
(f[nxt][j < m - 1][b][S | 1 << j] += x) %= P;
if(a | (S >> j & 1)) (f[nxt][a & (j < m - 1)][b][S] += x) %= P;
else if(!b) (f[nxt][0][1][S] += x) %= P;
}
}
int as = 0;
rep(b, 0, 1) For(S, 0, 1 << m) (as += f[n * m][0][b][S]) %= P;
cout << as;
return 0;
}