解题思路

插头 $DP$。参考论文《基于连通性状态压缩的动态规划问题》中的方法。从上往下，从左到右，逐格进行动态规划。$dp[i][j][S]$表示当前已经决策完格子$（i，j）$后轮廓线上从左到右$m + 1$个插头是否存在以及它们的连通性为$S$的方案总数。（插头：一个格子某个方向的插头存在表示这个格子在这个方向与相邻格子相连。）轮廓线：已决策格子和未决策格子的分界线。由于是有顺序的逐格$dp$，所以轮廓线与已决策格子的接触边数最多就是$m + 1$，而这些接触的边所对应的已决策格子在接触边这一方向上是否有插头且插头间的连通性是需要记录的信息。根据轮廓线上一方向上是否有插头且与它相连的插头的情况来描述轮廓线的状态。用最小表示法。从左到右依次标记：无插头标记 $0$，有插头标记一个正整数，其中连通的插头标记同一个数字。关键在于状态转移的时候根据上一个状态的情况与当前考虑的那一个格子的情况，计算出转移后的状态的最小表示。自己画一个图并画上一条轮廓线就会发现，影响状态转移的就是当前轮廓线上面下一个需要决策的格子（$i$，$j + 1$）的左插头和上插头（转移后轮廓线上相应位置的状态就变成是（$i$，$j + 1$）下插头和右插头的状态）。

标程

#include <iostream>
#include <cstring>
#include <map>
#define LL long long
using namespace std;

map<int, int> IH;
int n, m, H[40000], s;
LL d[2][40000];
char ch[10][10];

void getHash(int k, int x, int y) // y 未匹配的右括号 
{
    if (y < 0 || y > m - k + 1) return;
    if (k == m + 1) {
        IH[x] = s;
        H[s++] = x;
    }
    getHash(k + 1, x << 2, y);
    getHash(k + 1, x << 2 | 2, y - 1);    
    getHash(k + 1, x << 2 | 3, y + 1);
}

LL DP()
{
    d[1][0] = 1;
    for (int i = 1, cur = 1; i <= n; i++, cur ^= 1)
    {
        for (int j = 0; j < m; j++, cur ^= 1)
        {
            memset(d[cur^1], 0, sizeof(d[cur^1]));
            for (int k = 0; k < s; k++)
            {
                long long temp = d[cur][k];
                if (!temp) continue;
                int t = H[k], x = t >> (j << 1) & 3, y = t >> ((j + 1) << 1) & 3;
                if (ch[i][j] == '.')
                {
                    if (x + y == 3 || x + y == 2)
                    {
                        d[cur^1][k] += temp;
                        d[cur^1][IH[t ^ ((x | y) << (j << 1)) ^ ((x | y) << ((j + 1) << 1))]] += temp;
                    }
                    if (x == 3 && y == 2)
                    {
                        d[cur^1][IH[t ^ (x << (j << 1)) ^ (y << ((j + 1) << 1))]] += temp;
                    } 
                    if (x == 0 && y == 0)
                    {
                        d[cur^1][IH[t ^ (14 << (j << 1))]] += temp;
                    }
                    if (x == 2 && y == 2)
                    {
                        for (int ii = j + 2, jj = 0; ii <= m; ii++)
                        {
                            if ((t >> (ii << 1) & 3) == 2) jj++;
                            if ((t >> (ii << 1) & 3) == 3) jj--;
                            if (jj < 0)
                            {
                                d[cur^1][IH[t ^ (2 << (j << 1)) ^ (2 << ((j + 1) << 1)) ^ (1 << (ii << 1))]] += temp;
                                break;
                            }
                        }   
                    }
                    if (x == 3 && y == 3)
                    {
                        for (int ii = j - 1, jj = 0; ii >= 0; ii--)
                        {
                            if ((t >> (ii << 1) & 3) == 3) jj++;
                            if ((t >> (ii << 1) & 3) == 2) jj--;
                            if (jj < 0)
                            {
                                d[cur^1][IH[t ^ (3 << (j << 1)) ^ (3 << ((j + 1) << 1)) ^ (1 << (ii << 1))]] += temp;
                                break;
                            }
                        }   
                    }
                }
                else
                {
                    if ((x | y) == 0)
                    {
                        d[cur^1][k] += temp;
                    }
                }
            }
        }
        memset(d[cur^1], 0, sizeof(d[cur^1]));
        for (int j = 0; H[j] < (1 << (m << 1)); j++)
        {
            d[cur^1][IH[H[j] << 2]] = d[cur][j];
        }
        if (i == n)
        {
            return d[cur][IH[2 | (3 << ((m - 1) << 1))]];   
        } 
    }
}

int main()
{
    while (cin >> n >> m)
    {
        s = 0;
        memset(H, 0, sizeof(H));
        IH.clear();
        memset(d, 0, sizeof(d));
        if (n == 0) return 0;
        for (int i = 1; i <= n; i++) cin >> ch[i];
        getHash(0, 0, 0); 
        cout << DP() << endl;
    }
    return 0; 
}