http://acm.buaa.edu.cn/contest/116/problem/F/

http://acm.buaa.edu.cn/problem/746/

http://www.xuebuyuan.com/1798536.html

必须经过 | 可以经过。。 参考 FZU 1977. Pandora adventure

http://user.qzone.qq.com/251815992/blog/1441374326

格子存储四个方向的通行信息。。参考 ZOJ 2126. Rocket Mania

http://user.qzone.qq.com/251815992/blog/1441548754 ;

（但需要注意的是！。。这里是回路。。所以不允许插头在任意位置中断！）

const int N = 12, M = 1 << 20, _M = 3; int n, m; int b[N+1], bb[N+1]; LL encode(){ FLC(bb, -1); int n = 1; bb[0] = 0; LL s = 0; DWN(i, m+1, 0){ if (!~bb[b[i]]) bb[b[i]] = n++; b[i] = bb[b[i]]; s <<= _M; s |= b[i]; } return s; } void decode(LL s){ REP(i, m+1){ b[i] = s & _U(_M); s >>= _M; } } const int Prime = 9979; int d; struct hashTable{ LL state[M]; int key[M]; int sz; int hd[Prime], nxt[M]; void clear(){ sz = 0; FLC(hd, -1); } void push(){ LL s = encode(); int x = s % Prime; for (int i=hd[x];~i;i=nxt[i]){ if (state[i] == s){ INC(key[i], d); return; } } state[sz] = s; key[sz] = d; nxt[sz] = hd[x]; hd[x] = sz; ++sz; assert(sz < M); } void roll(){ REP(ii, sz) state[ii] <<= _M; } } H[2]; int src, des; int A[N+1][N+1], tx, ty; bool isBlock(int s){return s & 1;} bool isMust(int s){return s & 2;} bool isRight(int s){return s & 4;} bool isLeft(int s){return s & 8;} bool isDown(int s){return s & 16;} bool isUp(int s){return s & 32;} void init(){ tx = -1, ty = -1; RD(n, m); REP_2(i, j, n, m) if (isMust(RD(A[i][j]))) tx = i, ty = j; REP(i, m) A[n][i] = 1; REP(i, n) A[i][m] = 1; } void solve(){ src = 0, des = 1; H[des].clear(); RST(b); d = 1; H[des].push(); int z = 0; REP(i, n){ REP(j, m){ if (isBlock(A[i][j])) continue; swap(src, des); H[des].clear(); //cout << i << " " << j << " "<< H[src].sz << endl; REP(ii, H[src].sz){ decode(H[src].state[ii]); d = H[src].key[ii]; int lt = b[j], up = b[j+1]; bool dn = isDown(A[i][j]) && isUp(A[i+1][j]) && !isBlock(A[i+1][j]); bool rt = isRight(A[i][j]) && isLeft(A[i][j+1]) && !isBlock(A[i][j+1]); if (lt && up){ if (lt == up){ if (i*m+j>=tx*m+ty){ int cnt = 0; REP(jj, m+1) if (b[jj]) ++cnt; // ? if (cnt == 2) INC(z, d); } } else{ b[j] = b[j+1] = 0; REP(jj, m+1) if (b[jj] == lt) b[jj] = up; H[des].push(); } } else if (lt || up){ int t = lt | up; if (dn){ b[j] = t; b[j+1] = 0; H[des].push(); } if (rt){ b[j] = 0; b[j+1] = t; H[des].push(); } } else{ if (!isMust(A[i][j])){ H[des].push(); } if (dn && rt){ b[j] = b[j+1] = N-1; H[des].push(); } } } } H[des].roll(); } printf("%d\n", z); } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif Rush{ init(); solve(); } }