干了一天啊！！！插头DP入门。
代码如下：
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 typedef long long LL; 10 11 const int N = 15; 12 const int M = 1666666; 13 LL pw[N], dp[2][M]; 14 int stk[2][M], top[2]; 15 char mat[N][N]; 16 bool vis[M]; 17 18 void PRE() { 19 pw[0] = 1; 20 for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * 3; 21 } 22 23 inline int getst(int st, int k) { return st / pw[k] % 3;} 24 inline void print(int st, int n) { for (int i = n; i >= 0; i--) printf("%d", getst(st, i));} 25 26 LL work(int n, int m) { 27 bool fi = true; 28 int cur = 0, ei, ej, nx, st, hi, lo; 29 memset(dp, 0, sizeof(dp)); 30 memset(vis, 0, sizeof(vis)); 31 memset(top, 0, sizeof(top)); 32 for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (mat[i][j] == '.') ei = i, ej = j; 33 for (int i = 0; i < n; i++) { 34 for (int j = 0; j < m; j++) { 35 /************* debug ****************/ 36 //cout << i << ' ' << j << ' ' << top[cur] << endl; 37 //for (int k = 0; k < top[cur]; k++) { 38 //st = stk[cur][k]; 39 //print(st, m); cout << "~" << dp[cur][st] << ' '; 40 //} 41 //cout << endl; 42 /************************************/ 43 if (i == ei && j == ej) return dp[cur][pw[m] << 1 | 1]; 44 for (int k = 0; k < top[cur]; k++) vis[stk[cur][k]] = false; 45 cur ^= 1; 46 for (int k = 0; k < top[cur]; k++) dp[cur][stk[cur][k]] = 0; 47 top[cur] = 0; 48 if (mat[i][j] == '*') { 49 if (fi) continue; 50 for (int k = 0; k < top[cur ^ 1]; k++) { 51 st = stk[cur ^ 1][k]; 52 if (getst(st, m)) continue; 53 nx = st * 3; 54 dp[cur][nx] += dp[cur ^ 1][st]; 55 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true; 56 } 57 } else { 58 if (fi) { 59 dp[cur][5] = 1; 60 vis[stk[cur][top[cur]++] = 5] = true; 61 fi = false; 62 } else { 63 for (int k = 0; k < top[cur ^ 1]; k++) { 64 st = stk[cur ^ 1][k]; 65 lo = getst(st, 0), hi = getst(st, m); 66 if (lo == 0) { 67 if (hi == 0) { 68 nx = st * 3 + 5; 69 dp[cur][nx] += dp[cur ^ 1][st]; 70 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true; 71 } else if (hi == 1) { 72 if (i == 0 || mat[i - 1][j] == '*') continue; 73 nx = (st * 3 + 1) % pw[m + 1]; 74 dp[cur][nx] += dp[cur ^ 1][st]; 75 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true; 76 nx = (st * 3 + 3) % pw[m + 1]; 77 dp[cur][nx] += dp[cur ^ 1][st]; 78 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true; 79 } else { 80 if (i == 0 || mat[i - 1][j] == '*') continue; 81 nx = (st * 3 + 2) % pw[m + 1]; 82 dp[cur][nx] += dp[cur ^ 1][st]; 83 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true; 84 nx = (st * 3 + 6) % pw[m + 1]; 85 dp[cur][nx] += dp[cur ^ 1][st]; 86 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true; 87 } 88 } else if (lo == 1) { 89 if (j == 0 || mat[i][j - 1] == '*') continue; 90 if (hi == 0) { 91 nx = st * 3 % pw[m + 1]; 92 dp[cur][nx] += dp[cur ^ 1][st]; 93 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true; 94 nx = (st * 3 - 2) % pw[m + 1]; 95 dp[cur][nx] += dp[cur ^ 1][st]; 96 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true; 97 } else if (hi == 1) { 98 if (i == 0 || mat[i - 1][j] == '*') continue; 99 int cnt = 0, i = m - 1, t;100 for ( ; i >= 0; i--) {101 t = getst(st, i);102 if (t == 1) cnt++;103 if (t == 2) {104 if (cnt) cnt--;105 else break;106 }107 }108 nx = (st - pw[i] - 1) * 3 % pw[m + 1];109 //print(st, m); putchar(' '); print(nx, m); puts("");110 dp[cur][nx] += dp[cur ^ 1][st];111 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true;112 } else {}113 } else {114 if (j == 0 || mat[i][j - 1] == '*') continue;115 if (hi == 0) {116 nx = st * 3 % pw[m + 1];117 dp[cur][nx] += dp[cur ^ 1][st];118 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true;119 nx = (st * 3 - 4) % pw[m + 1];120 dp[cur][nx] += dp[cur ^ 1][st];121 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true;122 } else if (hi == 1) {123 if (i == 0 || mat[i - 1][j] == '*') continue;124 nx = st / 3 * 9 % pw[m + 1];125 dp[cur][nx] += dp[cur ^ 1][st];126 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true;127 } else {128 if (i == 0 || mat[i - 1][j] == '*') continue;129 int cnt = 0, i = 1, t;130 for ( ; i <= m; i++) {131 t = getst(st, i);132 if (t == 2) cnt++;133 if (t == 1) {134 if (cnt) cnt--;135 else break;136 }137 }138 nx = (st + pw[i] - 2) * 3 % pw[m + 1];139 dp[cur][nx] += dp[cur ^ 1][st];140 if (!vis[nx]) vis[stk[cur][top[cur]++] = nx] = true;141 }142 }143 }144 }145 }146 }147 }148 return 0;149 }150 151 int main() {152 //freopen("in", "r", stdin);153 //freopen("out", "w", stdout);154 //time_t t1 = clock();155 int n, m;156 PRE();157 //cout << (double) (clock() - t1) / CLOCKS_PER_SEC << endl;158 while (cin >> n >> m) {159 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cin >> mat[i][j]; mat[i][m] = 0;}160 cout << work(n, m) << endl;161 //cout << (double) (clock() - t1) / CLOCKS_PER_SEC << endl;162 }163 return 0;164 }
——written by Lyon