FZU_1977
对于必须要走的点，那么在那个点就一定要有插头。而对于不必走的点，如果dp到该点时没有插头，那么既可以在这个点放两个插头开辟一个新的连通分量，也可以不放插头，相当于不经过这个点。
此外由于回头只能有一条，而形成回路的最后一个点又是不确定的，所以可以再额外记录一下当前是否已经形成了回路，这样如果已经形成了回路而后面又遇到了插头或者必须要走的点，那么这个方案自然就是不合法的。
#include<stdio.h> #include<string.h> #define MAXD 15 #define HASH 30007 #define SIZE 500010 int N, M, maze[MAXD][MAXD], ch[MAXD], code[MAXD], isend; char b[MAXD]; struct Hashmap { int head[HASH], next[SIZE], size; long long state[SIZE], f[SIZE]; void init() { memset(head, -1, sizeof(head)); size = 0; } void push(long long st, long long ans) { int i, h = st % HASH; for(i = head[h]; i != -1; i = next[i]) if(st == state[i]) { f[i] += ans; return ; } state[size] = st, f[size] = ans; next[size] = head[h]; head[h] = size ++; } }hm[2]; void decode(int *code, int m, long long st) { int i; isend = st & 7; for(i = m; i >= 0; i --) { st >>= 3; code[i] = st & 7; } } long long encode(int *code, int m) { int i, cnt = 1; long long st = 0; memset(ch, -1, sizeof(ch)); ch[0] = 0; for(i = 0; i <= m; i ++) { if(ch[code[i]] == -1) ch[code[i]] = cnt ++; code[i] = ch[code[i]]; st <<= 3; st |= code[i]; } st <<= 3; st |= isend; } void init() { int i, j; scanf("%d%d", &N, &M); memset(maze, 0, sizeof(maze)); for(i = 1; i <= N; i ++) { scanf("%s", b + 1); for(j = 1; j <= M; j ++) { if(b[j] == 'O') maze[i][j] = 2; else if(b[j] == '*') maze[i][j] = 1; } } } void shift(int *code, int m) { int i; for(i = m; i > 0; i --) code[i] = code[i - 1]; code[0] = 0; } void dpblock(int i, int j, int cur) { int k; for(k = 0; k < hm[cur].size; k ++) { decode(code, M, hm[cur].state[k]); code[j - 1] = code[j] = 0; if(j == M) shift(code, M); hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]); } } void dpblank(int i, int j, int cur) { int k, t, left, up; for(k = 0; k < hm[cur].size; k ++) { decode(code, M, hm[cur].state[k]); left = code[j - 1], up = code[j]; if(isend) { if(left || up || maze[i][j] == 2) continue; code[j - 1] = code[j] = 0; if(j == M) shift(code, M); hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]); continue; } if(left && up) { if(left == up) { code[j - 1] = code[j] = 0, isend = 1; if(j == M) shift(code, M); hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]); } else { code[j - 1] = code[j] = 0; for(t = 0; t <= M; t ++) if(code[t] == up) code[t] = left; if(j == M) shift(code, M); hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]); } } else if(left || up) { if(maze[i][j + 1]) { code[j - 1] = 0, code[j] = left + up; hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]); } if(maze[i + 1][j]) { code[j - 1] = left + up, code[j] = 0; if(j == M) shift(code, M); hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]); } } else { if(maze[i + 1][j] && maze[i][j + 1]) { code[j - 1] = code[j] = 13; hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]); } if(maze[i][j] == 1) { code[j - 1] = code[j] = 0; if(j == M) shift(code, M); hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]); } } } } void solve() { int i, j, cur = 0; long long ans = 0; hm[cur].init(); hm[cur].push(0, 1); for(i = 1; i <= N; i ++) for(j = 1; j <= M; j ++) { hm[cur ^ 1].init(); if(maze[i][j] == 0) dpblock(i, j, cur); else dpblank(i, j, cur); cur ^= 1; } for(i = 0; i < hm[cur].size; i ++) ans += hm[cur].f[i]; printf("%I64d\n", ans); } int main() { int t, tt; scanf("%d", &t); for(tt = 0; tt < t; tt ++) { init(); printf("Case %d: ", tt + 1); solve(); } return 0; }