[POJ 1739 Tony’s Tour]基于连通性的状态压缩动态规划、男人8题

【题目大意】

给定一个M*N的矩阵，问从左下角经过所有非障碍点到达右下角有多少种方案？

【算法分析】

我们先把图改一下。

比如说样例

..

..

那么改成

……

.####.

.#..#.

......

这样转化以后，就变成求哈密顿回路的方案数了。

因为最外面那一圈必须走。

于是用Cdq的论文的方法解决。

【其它】1A，hash开到10003是47MS,开到473 是32MS。。。果然我的怎么说都比较慢啊。。。

【CODE】

#include #include #include #include #define cf(x) (1<<(x))
using namespace std;
const int key=473;
const int INF=0x7FFFFFFF;
typedef long long LL;
struct gtp{int y,next;}g[200000];
int m,n,ng,pg,e,mx,my;
char c[15][15];
LL fl[2][200000],ans;
int sl[2][200000];
int tot[2],ls[key];

inline void init(){e=0;memset(ls,0,sizeof(ls));}
inline void addedge(int x,int y){e++; g[e].y=y; g[e].next=ls[x]; ls[x]=e;}
inline int ChaTou(int t1,int t2){
    if (!t1 && !t2) return 0;
    if (t1) return 1;
    return 2;
}   

void add(int s,LL f){
    int st=s; if (st>=key) st%=key;
    for (int t=ls[st];t;t=g[t].next)
      if (sl[ng][g[t].y]==s){
          fl[ng][g[t].y]+=f;
          return;
      }
    sl[ng][++tot[ng]]=s;
    fl[ng][tot[ng]]=f;
    addedge(st,tot[ng]);
}

bool input(){
    ng=1; pg=0; ans=0; tot[0]=0; tot[1]=0;
    scanf("%d%d",&m,&n);
    if (!m && !n) return false;
    int i,j;
    char ch;
    memset(c,’#’,sizeof(c));
    for (i=0;i      for (j=0;j        for (ch=getchar();ch!=’#’&&ch!=’.’;ch=getchar());
        c[i+2][j+2]=ch;
      }
    m+=2; n+=4;
    for (j=0;j    for (i=0;i    for (i=0;i    c[m-1][1]=’.’; c[m-1][n-2]=’.’;
    init();
    add(1+cf((n<<1)+1),1);
    mx=0; my=0;
    for (i=0;i      for (j=0;j        if (c[i][j]==’.’){
            mx=i;
            my=j;
        }   
    return true;
}   

void No(int j){
    int k,t1,t2;
    for (k=1;k<=tot[pg];k++){
        int &s=sl[pg][k];
        if ((s&cf((j<<1)))||(s&cf((j<<1)+1))||(cf((n<<1))&s)||(cf((n<<1)+1)&s)) continue;
        add(s,fl[pg][k]);
    }   
}

void Yes(int I,int j){
    int k,lct,uct,ts,i,top,ct;
    for (k=1;k<=tot[pg];k++){
        int &s=sl[pg][k];
        LL &f=fl[pg][k];
        uct=ChaTou(s&cf((j<<1)),s&cf((j<<1)+1));
        lct=ChaTou(s&cf((n<<1)),s&cf((n<<1)+1));
        if (!j && lct) continue;
        ts=(INF-cf((j<<1))-cf((j<<1)+1)-cf((n<<1))-cf((n<<1)+1))&s;
        switch (lct){
            case 0:
                switch (uct){
                    case 0:
                        add(ts|cf((j<<1))|cf((n<<1)+1),f);
                        break;
                    case 1:
                        add(ts|cf((j<<1)),f);
                        add(ts|cf((n<<1)),f);
                        break;
                    case 2:
                        add(ts|cf((j<<1)+1),f);
                        add(ts|cf((n<<1)+1),f);
                        break;
                }   
                break;
            case 1:
                switch (uct){
                    case 0:
                        add(ts|cf((j<<1)),f);
                        add(ts|cf((n<<1)),f);
                        break;
                    case 1:
                        top=0;
                        for (i=j;;i++){
                            ct=ChaTou(s&cf((i<<1)),s&cf((i<<1)+1));
                            if (ct==1) top++;
                            if (ct==2) top–;
                            if (top==0) break;
                        }
                        add((ts^cf((i<<1)+1))|cf((i<<1)),f);
                        break;
                    case 2:
                        if (I==mx && j==my && ts==0) ans+=f;
                        break;
                }   
                break;
            case 2:
                switch (uct){
                    case 0:
                        add(ts|cf((j<<1)+1),f);
                        add(ts|cf((n<<1)+1),f);
                        break;
                    case 1:
                        add(ts,f);
                        break;
                    case 2:
                        top=0;
                        for (i=j;;i–){
                            ct=ChaTou(s&cf((i<<1)),s&cf((i<<1)+1));
                            if (ct==1) top++;
                            if (ct==2) top–;
                            if (top==0) break;
                        }   
                        add((ts^cf((i<<1)))|cf((i<<1)+1),f);
                        break;
                }   
                break;
        }   
    }   
}            

void dp(){
    for (int i=0;i      for (int j=0;j          if (!i && !j) continue;
          ng=1-ng;
          pg=1-pg;
          tot[ng]=0;
          init();
          if (c[i][j]==’#’) No(j);
                       else Yes(i,j);
      }
}   

int main(){
    while (input()){
      dp();
      cout << ans << endl;
}   
    return 0;   
}