首先看到题很容易能想到插头 DP。但是数据范围很大，\(n,m \le 30\)，直接压会很爆炸。不过发现合法状态很少，因为轮廓线上最多同时只能有三个插头，所以大部分状态都是不合法的。
一种方法是直接哈希表记录合法状态，可以参考其他题解，另一种方法是直接记录这三个插头的位置，而不是记录每个位置有没有插头。
发现 \(30\) 这个数正好能压到 \(32\) 中，所以我们可以这样压缩状态：前两位代表已经放了几个插头（\(3=2^2-1\)），后面有三个五位记录三个插头的位置（\(31=2^5-1\)），这样一个状态最大只有 \(2^{17}-1=131071\)。
转移就比较轻松了，分五种情况：
- 这一格是障碍：直接转移过去。
- 没有向右和向下的插头：这一格可以不放，可以为一个 L 的起点。
- 只有向下的插头：那么说明这肯定是 L 上面转移下来的，可以继续向下延伸，或者向右拐。
- 只有向右的插头：那么说明一定是 L 拐弯之后过来的，可以继续向右延伸，或者在这里结束。
- 同时有向右和向下的插头：此种情况不合法，直接跳过。
这样实现略麻烦，我使用了一个结构体来封装状态，自认为还是挺清新的）这样就可以比较方便的转移，具体看代码吧。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct DATA {
int cnt, a, b, c;
DATA(int q) { // 将 int 转换为状态
cnt = q & 3;
a = q >> 2 & 31;
b = q >> 7 & 31;
c = q >> 12 & 31;
}
DATA(int cnt, int a, int b, int c) : cnt(cnt), a(a), b(b), c(c) {}
operator int() { // 将状态转换为 int
if (a > b) swap(a, b);
if (b > c) swap(b, c);
if (a > b) swap(a, b);
return cnt | (a << 2) | (b << 7) | (c << 12);
}
DATA replace(int a, int b, int d = 0) { // 替换插头的位置，d 代表 cnt 是否加 1
DATA c = *this;
if (c.a == a) c.a = b;
else if (c.b == a) c.b = b;
else if (c.c == a) c.c = b;
c.cnt += d;
return c;
}
};
int n, m;
const int T = 10007;
struct Hash { // 哈希表
int fst[T], nxt[T], tot, v[T], k[T];
void insert(int d, int vv) {
int h = d % T;
v[++tot] = vv;
k[tot] = d;
nxt[tot] = fst[h];
fst[h] = tot;
}
int find(int d) {
int h = d % T;
int p = fst[h];
while (p && k[p] != d) p = nxt[p];
return v[p];
}
void clear() {
tot = 0;
memset(fst, 0, sizeof fst);
}
}mp[2];
long long f[2][MAXN], cnt;
void S(int d, int a, long long b) { // 更新答案函数
int q = mp[d].find(a);
if (q) f[d][q] += b;
else mp[d].insert(a, ++cnt), f[d][cnt] = b;
}
char ch[44][44];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", ch[i] + 1);
f[0][1] = 1, mp[0].insert(DATA{0, 0, 0, 0}, 1);
for (int i = 1, t = 0; i <= n; i++) {
for (int j = 1; j <= mp[t].tot; j++) { // 新一行状态要向右平移
DATA ori = mp[t].k[j];
if (ori.a) ori.a++;
if (ori.b) ori.b++;
if (ori.c) ori.c++;
mp[t].k[j] = ori;
}
for (int j = 1; j <= m; j++) {
t ^= 1, cnt = 0;
mp[t].clear();
for (int k = 1; k <= mp[t ^ 1].tot; k++) {
DATA s = mp[t ^ 1].k[k];
long long ans = f[t ^ 1][mp[t ^ 1].v[k]];
int r = s.a == j || s.b == j || s.c == j,
d = s.a == j + 1 || s.b == j + 1 || s.c == j + 1;
if (ch[i][j] == '#') { // case 1
S(t, s, ans);
} else if (!r && !d) { // case 2
S(t, s, ans);
if (ch[i + 1][j] == '.' && s.cnt < 3)
S(t, s.replace(0, j, 1), ans);
} else if (!r && d) { // case 3
if (ch[i + 1][j] == '.') S(t, s.replace(j + 1, j), ans);
if (ch[i][j + 1] == '.') S(t, s, ans);
} else if (r && !d) { // case 4
if (ch[i][j + 1] == '.') S(t, s.replace(j, j + 1), ans);
S(t, s.replace(j, 0), ans);
} else if (r && d) { // case 5
"go to hell";
}
}
}
if (i == n) {
printf("%lld\n", f[t][mp[t].find(DATA{3, 0, 0, 0})]);
}
}
return 0;
}