http://acm.pku.edu.cn/JudgeOnline/problem?id=1739
基于连通性状态压缩的动态规划(名字真长- -！)其实不算太难，以前都被它吓住了。
hyf教了一次后，印象极其深刻，回路、路径条数啥的从此再也不用向美国（雾）进口了。
简要的说：f[i][j][k]表示在（i，j）这个格子的时候，m+1个插头的情况是k，然后根据(i,j)左边和上边插头（括号？）的情况进行连接，然后转移到下一个格子。一个合法的状态是一个括号表达式，有左括号，右括号和空格，且左右括号匹配。一个左括号和一个相应的右括号表示这两个地方的路径是连在一起的。转移的时候分情况讨论。
处理的时候先把所有合法的状态都dfs出来，转移的时候就方便了。。
PS：居然惊喜地进入了status第一页？！。。。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 8
#define BLANK 0
#define LEFT 1
#define RIGHT 2
#define MAXSTATE 174420
#define MAXSTATEAMOUNT 835
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define ll long long

using namespace std;

int n,m;
char map[MAXN+1][MAXN+1];
int nState = 0;
int State[MAXSTATEAMOUNT+1];
int id[MAXSTATE+1];
int Tx, Ty, FinalState;
ll f[MAXN+1][MAXN+1][MAXSTATEAMOUNT+1];
ll ans;
void Reset(){
     nState = 0, Tx = -1;
     memset(f, 0, sizeof(f));
     ans = 0;
}

bool Init(){
     scanf("%d%d",&n,&m);
     if (!n) return false;
     Reset();
     for (int i = n-1; i>=0; i--){
         scanf("%s", map[i]);
         if (Tx == -1)
         for (int j = m-1; j>=0; j--)
             if (map[i][j] == '.'){
                Tx = i, Ty = j;
                break;
             }
         for (int j = 0; j<m; j++)
             if (map[i][j] == '.') map[i][j] = 0;
             else map[i][j] = 1;
     }
     return true;
}

void dfs(int pos, int r_bracket, int state){
     if (pos < 0){
        State[nState] = state;
        id[state] = nState;
        /*
        printf("%d: ", nState);
        for (int i = 0; i<=m; i++)
            printf("%d ", buffer[i]);
        printf("\n");
        */
        nState ++;
        return;
     }
     if (pos >= r_bracket) // blank
        dfs(pos - 1, r_bracket, (state << 2));
     if (pos > r_bracket) // right bracket
        dfs(pos - 1, r_bracket + 1, (state << 2) | RIGHT);
     if (r_bracket) // left bracket
        dfs(pos - 1, r_bracket - 1, (state << 2) | LEFT);
}

#define MASK 3
#define Get(state, p) (((state) >> (p<<1)) & MASK)

inline bool OK(int i, int j, int state){
     if (Get(state, j) == 1 && Get(state, j+1) == 2 && !(i == Tx && j == Ty)) return false;
     for (int k = 0; k<j; k++)
         if ((map[i][k] || map[i+1][k]) && Get(state, k)) return false;
     if (((j && map[i][j-1]) || (map[i][j])) && Get(state, j)) return false;
     for (int k = j+1; k<=m; k++)
         if (((i && map[i-1][k-1]) || (map[i][k-1])) && Get(state, k)) return false;
     return true;
}

inline int Modify(int state, int p, int v){
    return state - (((state >> (p << 1)) & MASK) << (p << 1)) + (v << (p << 1));
}

inline int FindRight(int p, int state){
    int cnt = 0, t;
    for (int i = p; i<=m; i++){
        t = Get(state,i);
        if (t == 1) cnt++;
        if (t == 2) cnt--;
        if (cnt == 0) return i;
    }
    return -1;
}

inline int FindLeft(int p, int state){
    int cnt = 0, t;
    for (int i = p; i>=0; i--){
        t = Get(state, i);
        if (t == 2) cnt++;
        if (t == 1) cnt--;
        if (cnt == 0) return i;
    }
    return -1;
}

void Solve(){
     dfs(m, 0, 0);
     f[0][0][id[(1 << 2) + (2 << (2 * m))]] = 1;
     FinalState = (1 << (2 * Ty)) + (2 << (2 * (Ty+1)));
     int p, q, tmp, tmp2, state, v, i, j, k;
     ll *a;
     for (i = 0; i < n; i++){
         for (j = 0; j < m; j++){
             a = f[i][j+1];
             for (k = 0; k < nState; k++)
                 if ((v = f[i][j][k])){
                     state = State[k];
                     p = Get(state, j), q = Get(state, j+1);
                     if (p == 0 && q == 0){
                        if (!map[i][j]){
                            tmp = Modify(Modify(state, j, 1), j+1, 2);
                            if (OK(i, j+1, tmp))
                               a[id[tmp]] += v;
                        }else
                             a[k] += v;
                     }else if(p == 0){ // conditions below ensured map[i][j] is empty, because there exists at least one bracket on one side of the grid (i,j)
                           if (OK(i, j+1, state))
                              a[k] += v;
                           tmp = Modify(Modify(state, j, q), j+1, 0);
                           if (OK(i, j+1, tmp))
                              a[id[tmp]] += v;
                     }else if (q == 0){
                           if (OK(i, j+1, state))
                              a[k] += v;
                           tmp = Modify(Modify(state, j, 0), j+1, p);
                           if (OK(i, j+1, tmp))
                              a[id[tmp]] += v;
                     }else{
                         tmp = Modify(Modify(state, j, 0), j+1, 0);
                         if (p == 1 && q == 1){
                               tmp2 = Modify(tmp, FindRight(j+1, state), 1);
                               if (OK(i, j+1, tmp2))
                                  a[id[tmp2]] += v;
                         }else if (p == 2 && q == 2){
                               tmp2 = Modify(tmp, FindLeft(j, state), 2);
                               if (OK(i, j+1, tmp2))
                                  a[id[tmp2]] += v;
                         }else if (p == 1 && q == 2){
                               if (i == Tx && j == Ty && state == FinalState){
                                  printf("%I64d\n", v);
                                  return;
                               }
                         }else if (p == 2 && q == 1){
                               if (OK(i, j+1, tmp))
                                  a[id[tmp]] += v;
                         }
                     }
                 }
         }
         for (int k = 0; k < nState; k++)
             if (Get(State[k], m) == 0 && OK(i+1, 0, tmp = (State[k] << 2)))
                f[i+1][0][id[tmp]] += f[i][m][k];
     }
     printf("%I64d\n", ans);
}

int main(){
    while (Init())
          Solve();
    return 0;
}