看到题目显然是插头(dp)，但是(n)和(m)的范围似乎不是很小。我们先不考虑复杂度设一下状态试试：
一共有三个连通分量，我们按照(1,2,3)的顺序来表示一下。轮廓线上(0)代表没有插头接入，(x)说明有第(x)个连通分量里的插头接入，需要在这里连下去。
我们设当前格子左边的一位轮廓线为(b_1)，上边的一位轮廓线为(b_2)。
-
如果(b_1 = b_2 = 0)：
-
当前格子可以选择不放。
-
当前格子也可以向下新建一个(L)。
-
-
如果(b1 = 0)且(b2 != 0)：
-
可以连下去。
-
也可以在这里拐弯向右。
-
-
如果(b1 != 0)且(b2 = 0)：
-
可以向右连下去。
-
也可以就此结束。
-
连通分量会出现中断的情况。比如你在很靠上的地方选两个(L)，又在最下面选了一个(L)，这时候可能会出现中间某些轮廓线上全都是(0)，遇到第三个分量的时候不好判断。这里我们在第(m+1)位上再放一个数，表示目前已经出现几个连通分量，就容易确定状态的可行性了。
状态和决策都很简单。下面我们看一下复杂度靠谱不靠谱。
一般逐格转移的插头(dp)复杂度是(O(NM*)状态总数上界())。一条轮廓线上最多有三个连通分量接入，所以用(0,1,2,3)四个数四进制表示。每个连通分量只可能接入一次（想一想，为什么），那么可以出现连通分量的选择就有(C_N^3)种。考虑三种连通分量各自的编号选择，状态总数就有(C_N^3 * 4^3=259840)种。运算次数大概是(2e8)左右，开着(O2)可以轻松卡过去。
（当然不开(O2)略微卡常也可以但是我懒=_=
(Code)：
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N = 30 + 5;
const int base = 999983;
const int M = 1000000 + 5;
int n, m, can_use[N][N];
int las, cur, cnt[2], nxt[M];
int head[M]; int dp[2][M], Hash[2][M];
void update (int zt, int val) {
int _zt = zt % base;
for (int i = head[_zt]; i; i = nxt[i]) {
if (Hash[cur][i] == zt) {
dp[cur][i] += val; return;
}
}
nxt[++cnt[cur]] = head[_zt];
head[_zt] = cnt[cur];
Hash[cur][cnt[cur]] = zt;
dp[cur][cnt[cur]] = val;
}
int get_val (int zt) {
int _zt = zt % base;
for (int i = head[_zt]; i; i = nxt[i]) {
if (Hash[cur][i] == zt) {
return dp[cur][i];
}
}
return 0;
}
int get_wei (int zt, int wei) {
return (zt >> (wei * 2)) % 4;
}
int alt_wei (int zt, int wei, int val) {
return zt - ((get_wei (zt, wei) - val) << (wei * 2));
}
void change_row () {
for (int i = 1; i <= cnt[cur]; ++i) {
int &zt = Hash[cur][i];
for (int k = m; k >= 1; --k) {
zt = alt_wei (zt, k, get_wei (zt, k - 1));
}
zt = alt_wei (zt, 0, 0);
}
}
void print_zt (int zt) {
for (int k = 0; k<= m + 1; ++k) {
cout << get_wei (zt, k) << " ";
}
}
void print (int x, int y) {
cout << "r = " << x << " c = " << y << endl;
for (int i = 1; i <= cnt[cur]; ++i) {
cout << "zt = ";
print_zt (Hash[cur][i]);
cout << "dp = " << dp[cur][i] << endl;
}
}
int solve () {
update (0, 1);
// print (0, 0);
for (int i = 1; i <= n; ++i) {
change_row ();
for (int j = 1; j <= m; ++j) {
las = cur, cur ^= 1, cnt[cur] = 0;
memset (head, 0, sizeof (head));
for (int k = 1; k <= cnt[las]; ++k) {
int zt = Hash[las][k];
int b1 = get_wei (zt, j - 1);
int b2 = get_wei (zt, j - 0);
int val = dp[las][k];
// print_zt (zt); cout << endl;
// cout << "b1 = " << b1 << " b2 = " << b2 << endl;
if (!can_use[i][j]) {
if (!b1 && !b2) {
update (zt, val);
}
} else {
if (b1 == 0 && b2 == 0) {
int b = get_wei (zt, m + 1), _zt = zt;
if (b < 3 && can_use[i + 1][j]) {
_zt = alt_wei (_zt, m + 1, b + 1); // 新建连通分量
_zt = alt_wei (_zt, j - 1, b + 1); // b1 那一位改为新分量编号
// print_zt (zt); cout << " -> "; print_zt (_zt); cout << endl;
update (_zt, val);
}
update (zt, val); // 这个格子不占用
}
if (b1 == 0 && b2 != 0) {
if (can_use[i + 1][j]) {
int _zt = zt;
_zt = alt_wei (_zt, j - 1, b2);
_zt = alt_wei (_zt, j - 0, 0);
// 0_b2 -> b2_0
// print_zt (zt); cout << " -> "; print_zt (_zt); cout << endl;
update (_zt, val);
}
if (can_use[i][j + 1]) {
update (zt, val);
// 0_b2 -> 0_b2
}
}
if (b1 != 0 && b2 == 0) {
if (can_use[i][j + 1]) {
int _zt = zt;
_zt = alt_wei (_zt, j - 1, 0);
_zt = alt_wei (_zt, j - 0, b1);
// b1_0 -> 0_b1
// print_zt (zt); cout << " -> "; print_zt (_zt); cout << endl;
update (_zt, val);
}
int _zt = alt_wei (zt, j - 1, 0);
// b1_0 -> 0_0
// print_zt (zt); cout << " -> "; print_zt (_zt); cout << endl;
update (_zt, val);
}
}
}
// print (i, j);
}
}
int fin = alt_wei (0, m + 1, 3);
return get_val (fin);
}
signed main () {
// freopen ("data.in", "r", stdin);
// freopen ("data.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int ch = getchar ();
if (ch != '.' && ch != '#') {
ch = getchar ();
}
if (ch == '.') can_use[i][j] = true;
// cout << can_use[i][j] << " ";
}
// cout << endl;
}
cout << solve () << endl;
}