题目链接：/problem?id=1739
完全可以用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为表大小 28int first[MOD],next[STA],size; 29LL f[STA],sta[STA]; 30void init(){ 31 size=0; 32 mem(first,-1); 33} 34void 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 { 51int k; 52LL sta; 53for(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 { 61LL i,cnt=1,sta=0; 62mem(ma,-1); 63ma[0]=0; 64for(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} 69return sta; 70 } 71 72 void getcode(LL sta) 73 { 74int i; 75for(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 { 83int k,t; 84LL cnt,x,y; 85for(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 {121int k;122for(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 {131int i,j,p;132hs[0].init();133hs[p=1].init();134hs[0].add(0,1);135for(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}144for(i=0;i<hs[!p].size;i++)145 if(hs[!p].sta[i]==0)return hs[!p].f[i];146return 0;147 }148 149 int main()150 {151 // freopen("in.txt","r",stdin);152int i,j;153LL ans;154char c;155while(~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}173return 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{ 28int first[MOD],next[STA],size; 29LL f[STA],sta[STA]; 30void init(){ 31 size=0; 32 mem(first,-1); 33} 34void 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 { 51int k; 52LL sta; 53for(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 { 61LL i,cnt=1,sta=0; 62mem(ma,-1); 63ma[0]=0; 64for(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} 69return sta; 70 } 71 72 void getcode(LL sta) 73 { 74int i; 75for(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 { 83int k,t; 84LL cnt,x,y; 85for(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){115if(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 {130int k;131for(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 {140int i,j,p;141hs[0].init();142hs[p=1].init();143hs[0].add(0,1);144for(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}153for(i=0;i<hs[!p].size;i++ )154 if(hs[!p].sta[i]==0)return hs[!p].f[i];155return 0;156 }157 158 int main()159 {160 // freopen("in.txt","r",stdin);161int i,j;162LL ans;163char c;164while(~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}182return 0;183 }
![[POJ3133]Manhattan Wiring 插头dp](https://2000zi.500zi.com/uploadfile/img/15/480/51f808d7703bde250761ce6b95e66fe9.jpg)
![[Poj3133]Manhattan Wiring （插头DP）](https://2000zi.500zi.com/uploadfile/img/15/480/a81f9e124c272d4bf3dbdde8cd3335b1.jpg)
