【POJ】【1739】Tony's Tour

插头DP

　　楼教主男人八题之一！

　　要求从左下角走到右下角的哈密顿路径数量。

　　啊嘞，我只会求哈密顿回路啊……这可怎么搞……

　　容易想到：要是把起点和重点直接连上就变成一条回路了……那么我们就连一下~

　　我们可以在整张图下面加两行：(例：3*5)

　　1 1 1 1 1

　　1 0 0 0 1

　　1 1 1 1 1

　　红色的是原来的起点和终点，下面紫色的路径将这两个点连了起来= =然后这题瞬间就变回了Formula 1那题……求哈密顿回路数量，so easy有没有~（其实不这样加也可以做，起点终点特判下就可以）

　　因为就变成原题了……我就试着默写了一次模板……结果好几个细节给挂了：

　　单插头的时候，两种状态转移都要判是否合法的= =！！！（sigh……做了一道HDU 1964直接就傻逼了……因为那题是没有障碍物的……）

　　两个插头都没有的时候的转移写错了……(┬＿┬)不可以乘p/q的……因为它俩都是0啊……

　　程序一开始的时候bit数组的初始化……

  1 Source Code
  2 Problem: 1739        User: sdfzyhy
  3 Memory: 2668K        Time: 125MS
  4 Language: G++        Result: Accepted
  5 
  6     Source Code
  7 
  8     //POJ 1739
  9     #include<cmath>
 10     #include<vector>
 11     #include<cstdio>
 12     #include<cstring>
 13     #include<cstdlib>
 14     #include<iostream>
 15     #include<algorithm>
 16     #define rep(i,n) for(int i=0;i<n;++i)
 17     #define F(i,j,n) for(int i=j;i<=n;++i)
 18     #define D(i,j,n) for(int i=j;i>=n;--i)
 19     #define pb push_back
 20     #define CC(a,b) memset(a,b,sizeof(a))
 21     using namespace std;
 22     int getint(){
 23         int v=0,sign=1; char ch=getchar();
 24         while(!isdigit(ch)) {if(ch=='-') sign=-1; ch=getchar();}
 25         while(isdigit(ch))  {v=v*10+ch-'0'; ch=getchar();}
 26         return v*sign;
 27     }
 28     const int N=1e7+10,INF=~0u>>2;
 29     const double eps=1e-8;
 30     typedef unsigned long long u64;
 31     /*******************template********************/
 32     const int M=100007;
 33     bool mp[15][15];
 34     int n,m,k;
 35     int tot[2],bit[15],hash[M],state[2][M];
 36     u64 dp[2][M],ans;
 37     #define debug
 38     void init(){
 39         CC(mp,0);
 40         CC(dp,0);
 41         tot[0]=dp[0][1]=1,ans=k=0;
 42         state[0][1]=0;
 43         char ch;
 44         F(i,1,n){
 45             scanf("%c",&ch);
 46             F(j,1,m){
 47                 scanf("%c",&ch);
 48                 mp[i][j]=ch=='.';
 49             }
 50         }
 51         n+=2;
 52         F(j,1,m) mp[n][j]=1;
 53         mp[n-1][1]=mp[n-1][m]=1;
 54     }
 55     void hash_in(int s,u64 sum){
 56         int p=s%M;
 57         while(hash[p]){
 58             if (state[k][hash[p]]==s){
 59                 dp[k][hash[p]]+=sum;
 60                 return;
 61             }
 62             p++;
 63             if (p==M) p=0;
 64         }
 65         hash[p]=++tot[k];
 66         state[k][hash[p]]=s;
 67         dp[k][hash[p]]=sum;
 68     }
 69     #define in hash_in(s,sum)
 70     void work(){
 71         F(i,1,n){
 72             F(j,1,m){
 73                 k^=1;
 74                 CC(hash,0);
 75                 tot[k]=0;
 76                 F(u,1,tot[1-k]){
 77                     int s=state[1-k][u];
 78                     u64 sum=dp[1-k][u];
 79                     int p=(s>>bit[j-1])&3,q=(s>>bit[j])&3;
 80                     if (!mp[i][j]){ if (!p && !q) in; }
 81                     else{
 82                         if (!p && !q){
 83                             if (!mp[i+1][j] || !mp[i][j+1]) continue;
 84                             s=s^(1<<bit[j-1])^(1<<bit[j]<<1),in;
 85                         }else if(!p && q){
 86                             if (mp[i][j+1]) in;
 87                             if (mp[i+1][j]) s=s^q*(1<<bit[j])^q*(1<<bit[j-1]),in;
 88                         }else if(p && !q){
 89                             if (mp[i+1][j]) in;
 90                             if (mp[i][j+1]) s=s^p*(1<<bit[j])^p*(1<<bit[j-1]),in;
 91                         }else if(p+q==2){
 92                             int nd=1;
 93                             F(u,j+1,m){
 94                                 int w=(s>>bit[u])&3;
 95                                 if (w==1) nd++;
 96                                 if (w==2) nd--;
 97                                 if (!nd){ s-=1<<bit[u]; break; }
 98                             }s=s^(1<<bit[j-1])^(1<<bit[j]),in;
 99                         }else if(p+q==4){
100                             int nd=1;
101                             D(u,j-2,1){
102                                 int w=(s>>bit[u])&3;
103                                 if (w==2) nd++;
104                                 if (w==1) nd--;
105                                 if (!nd){ s+=1<<bit[u]; break; }
106                             }s=s^(1<<bit[j-1]<<1)^(1<<bit[j]<<1),in;
107                         }else if(p==1 && q==2){
108                             if (i==n && j==m) ans+=sum;
109                         }else if(p==2 && q==1) s=s^(1<<bit[j-1]<<1)^(1<<bit[j]),in;
110                     }
111                 }
112             }
113             F(j,1,tot[k]) state[k][j]<<=2;
114         }
115         printf("%llu
",ans);
116     }
117     int main(){
118     #ifndef ONLINE_JUDGE
119         freopen("input.txt","r",stdin);
120     //    freopen("output.txt","w",stdout);
121     #endif
122         F(i,0,13) bit[i]=i<<1;
123         while(scanf("%d%d",&n,&m)!=EOF && n){
124             init();
125             work();
126         }
127         return 0;
128     }

View Code