# BUAA 746. 晴天小猪当导游

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

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

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

```