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;
}