POJ1739 Tony's Tour 插头DP(单条路径)

　　完全可以用Ural 1519 Formula 1 插头DP(单回路)的代码解决此题，只要把图修改一下:　

     ....           ........
     ....    ->     .######.
     ....           .#....#.
                    .#....#.
                    .#....#.
                    ........　

当然也可以在起点和终点独立处理插头。

修改建图：

View Code

  1 //STATUS:C++_AC_94MS_232KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 #include<map>
 13 using namespace std;
 14 #define LL long long
 15 #define pii pair<int,int>
 16 #define Max(a,b) ((a)>(b)?(a):(b))
 17 #define Min(a,b) ((a)<(b)?(a):(b))
 18 #define mem(a,b) memset(a,b,sizeof(a))
 19 #define lson l,mid,rt<<1
 20 #define rson mid+1,r,rt<<1|1
 21 const int N=15,INF=0x3f3f3f3f,MOD=4001,STA=1000010;
 22 const double DNF=100000000000;
 23 
 24 int g[N][N],code[N],ma[N];
 25 int n,m,ex,ey;
 26 
 27 struct Hash{     //Hash表,MOD为表长,STA为表大小
 28     int first[MOD],next[STA],size;
 29     LL f[STA],sta[STA];
 30     void init(){
 31         size=0;
 32         mem(first,-1);
 33     }
 34     void add(LL st,LL ans){
 35         int i,u=st%MOD;
 36         for(i=first[u];i!=-1;i=next[i]){
 37             if(sta[i]==st){
 38                 f[i]+=ans;
 39                 return;
 40             }
 41         }
 42         sta[size]=st;
 43         f[size]=ans;
 44         next[size]=first[u];
 45         first[u]=size++;
 46     }
 47 }hs[2];
 48 
 49 void shift(int p)
 50 {
 51     int k;
 52     LL sta;
 53     for(k=0;k<hs[!p].size;k++){
 54         sta=hs[!p].sta[k]<<3;
 55         hs[p].add(sta,hs[!p].f[k]);
 56     }
 57 }
 58 
 59 LL getsta()   //最小表示法
 60 {
 61     LL i,cnt=1,sta=0;
 62     mem(ma,-1);
 63     ma[0]=0;
 64     for(i=0;i<=m;i++){
 65         if(ma[code[i]]==-1)ma[code[i]]=cnt++;
 66         code[i]=ma[code[i]];
 67         sta|=(LL)code[i]<<(3*i);
 68     }
 69     return sta;
 70 }
 71 
 72 void getcode(LL sta)
 73 {
 74     int i;
 75     for(i=0;i<=m;i++){
 76         code[i]=sta&7;
 77         sta>>=3;
 78     }
 79 }
 80 
 81 void unblock(int i,int j,int p)
 82 {
 83     int k,t;
 84     LL cnt,x,y;
 85     for(k=0;k<hs[!p].size;k++){
 86         getcode(hs[!p].sta[k]);
 87         x=code[j],y=code[j+1];
 88         cnt=hs[!p].f[k];
 89         if(x && y){     //合并连通分量
 90             code[j]=code[j+1]=0;
 91             if(x!=y){
 92                 for(t=0;t<=m;t++)
 93                     if(code[t]==y)code[t]=x;
 94                 hs[p].add(getsta(),cnt);
 95             }
 96             else if(i==ex && j==ey){   //最后一个点特殊处理
 97                 hs[p].add(getsta(),cnt);
 98             }
 99         }
100 
101         else if(x&&!y || !x&&y){   //延续连通分量
102             t=x?x:y;
103             if(g[i+1][j]){
104                 code[j]=t;code[j+1]=0;
105                 hs[p].add(getsta(),cnt);
106             }
107             if(g[i][j+1]){
108                 code[j]=0;code[j+1]=t;
109                 hs[p].add(getsta(),cnt);
110             }
111         }
112         else if(g[i+1][j] && g[i][j+1]){  //创建新连通分量
113             code[j]=code[j+1]=8;
114             hs[p].add(getsta(),cnt);
115         }
116     }
117 }
118 
119 void block(LL j,int p)
120 {
121     int k;
122     for(k=0;k<hs[!p].size;k++){
123         getcode(hs[!p].sta[k]);
124         code[j]=code[j+1]=0;
125         hs[p].add(getsta(),hs[!p].f[k]);
126     }
127 }
128 
129 LL slove()
130 {
131     int i,j,p;
132     hs[0].init();
133     hs[p=1].init();
134     hs[0].add(0,1);
135     for(i=0;i<n;i++){
136         for(j=0;j<m;j++){
137             if(g[i][j])unblock(i,j,p);
138             else block(j,p);
139             hs[p=!p].init();
140         }
141         shift(p);   //换行移位
142         hs[p=!p].init();
143     }
144     for(i=0;i<hs[!p].size;i++)
145         if(hs[!p].sta[i]==0)return hs[!p].f[i];
146     return 0;
147 }
148 
149 int main()
150 {
151  //   freopen("in.txt","r",stdin);
152     int i,j;
153     LL ans;
154     char c;
155     while(~scanf("%d%d",&n,&m) && (n || m))
156     {
157         mem(g,0);
158         n+=2;m+=4;
159         for(i=0;i<m;i++)g[0][i]=1;
160         for(i=0;i<n;i++)g[i][0]=g[i][m-1]=1;
161         g[n-1][1]=g[n-1][m-2]=1;
162         ex=n-1,ey=m-1;
163         for(i=2;i<n;i++){
164             for(j=2;j<m-2;j++){
165                 scanf(" %c",&c);
166                 g[i][j]=(c=='.');
167             }
168         }
169         ans=slove();
170 
171         printf("%I64d\n",ans);
172     }
173     return 0;
174 }

建立独立插头：

View Code

  1 //STATUS:C++_AC_63MS_232KB
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<math.h>
  6 #include<iostream>
  7 #include<string>
  8 #include<algorithm>
  9 #include<vector>
 10 #include<queue>
 11 #include<stack>
 12 #include<map>
 13 using namespace std;
 14 #define LL long long
 15 #define pii pair<int,int>
 16 #define Max(a,b) ((a)>(b)?(a):(b))
 17 #define Min(a,b) ((a)<(b)?(a):(b))
 18 #define mem(a,b) memset(a,b,sizeof(a))
 19 #define lson l,mid,rt<<1
 20 #define rson mid+1,r,rt<<1|1
 21 const int N=15,INF=0x3f3f3f3f,MOD=4001,STA=1000010;
 22 const double DNF=100000000000;
 23 
 24 int g[N][N],code[N],ma[N];
 25 int n,m,sx,sy,ex,ey;
 26 
 27 struct Hash{
 28     int first[MOD],next[STA],size;
 29     LL f[STA],sta[STA];
 30     void init(){
 31         size=0;
 32         mem(first,-1);
 33     }
 34     void add(LL st,LL ans){
 35         int i,u=st%MOD;
 36         for(i=first[u];i!=-1;i=next[i]){
 37             if(sta[i]==st){
 38                 f[i]+=ans;
 39                 return;
 40             }
 41         }
 42         sta[size]=st;
 43         f[size]=ans;
 44         next[size]=first[u];
 45         first[u]=size++;
 46     }
 47 }hs[2];
 48 
 49 void shift(int p)
 50 {
 51     int k;
 52     LL sta;
 53     for(k=0;k<hs[!p].size;k++){
 54         sta=hs[!p].sta[k]<<3;
 55         hs[p].add(sta,hs[!p].f[k]);
 56     }
 57 }
 58 
 59 LL getsta()
 60 {
 61     LL i,cnt=1,sta=0;
 62     mem(ma,-1);
 63     ma[0]=0;
 64     for(i=0;i<=m;i++){
 65         if(ma[code[i]]==-1)ma[code[i]]=cnt++;
 66         code[i]=ma[code[i]];
 67         sta|=(LL)code[i]<<(3*i);
 68     }
 69     return sta;
 70 }
 71 
 72 void getcode(LL sta)
 73 {
 74     int i;
 75     for(i=0;i<=m;i++){
 76         code[i]=sta&7;
 77         sta>>=3;
 78     }
 79 }
 80 
 81 void unblock(int i,int j,int p)
 82 {
 83     int k,t;
 84     LL cnt,x,y;
 85     for(k=0;k<hs[!p].size;k++){
 86         getcode(hs[!p].sta[k]);
 87         x=code[j],y=code[j+1];
 88         cnt=hs[!p].f[k];
 89         if(x && y){
 90             if(x==y)continue;
 91             code[j]=code[j+1]=0;
 92             for(t=0;t<=m;t++)
 93                 if(code[t]==y)code[t]=x;
 94             hs[p].add(getsta(),cnt);
 95         }
 96         else if((x&&!y) || (!x&&y)){
 97             if((i==sx && j==sy) || (i==ex && j==ey)){
 98                 code[j]=code[j+1]=0;
 99                 hs[p].add(getsta(),cnt);
100             }
101             else {
102                 t=x?x:y;
103                 if(g[i+1][j]){
104                     code[j]=t;code[j+1]=0;
105                     hs[p].add(getsta(),cnt);
106                 }
107                 if(g[i][j+1]){
108                     code[j]=0;code[j+1]=t;
109                     hs[p].add(getsta(),cnt);
110                 }
111             }
112         }
113         else{
114             if(i==sx && j==sy){
115                if(g[i][j+1]){
116                     code[j+1]=8;
117                     hs[p].add(getsta(),cnt);
118                 }
119             }
120             else if(g[i+1][j] && g[i][j+1]){
121                 code[j]=code[j+1]=8;
122                 hs[p].add(getsta(),cnt);
123             }
124         }
125     }
126 }
127 
128 void block(LL j,int p)
129 {
130     int k;
131     for(k=0;k<hs[!p].size;k++){
132         getcode(hs[!p].sta[k]);
133         code[j]=code[j+1]=0;
134         hs[p].add(getsta(),hs[!p].f[k]);
135     }
136 }
137 
138 LL slove()
139 {
140     int i,j,p;
141     hs[0].init();
142     hs[p=1].init();
143     hs[0].add(0,1);
144     for(i=0;i<n;i++){
145         for(j=0;j<m;j++){
146             if(g[i][j])unblock(i,j,p);
147             else block(j,p);
148             hs[p=!p].init();
149         }
150         shift(p);
151         hs[p=!p].init();
152     }
153     for(i=0;i<hs[!p].size;i++ )
154         if(hs[!p].sta[i]==0)return hs[!p].f[i];
155     return 0;
156 }
157 
158 int main()
159 {
160  //   freopen("in.txt","r",stdin);
161     int i,j;
162     LL ans;
163     char c;
164     while(~scanf("%d%d",&n,&m) && (n || m))
165     {
166         mem(g,0);
167         sx=n-1,sy=0;
168         ex=n-1,ey=m-1;
169         for(i=0;i<n;i++){
170             for(j=0;j<m;j++){
171                 scanf(" %c",&c);
172                 g[i][j]=(c=='.');
173             }
174         }
175 
176         if(g[sx][sy]==0 || g[ex][ey]==0)ans=0;
177         else if(n==m && n==1)ans=1;
178         else ans=slove();
179 
180         printf("%I64d\n",ans);
181     }
182     return 0;
183 }