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

Posted by xiaodao
Category: 线上比赛
Tags: 插头DP