【POJ1739】Tony's Tour -插头dp

题意：

A square township has been divided up into n*m(n rows and m columns) square plots (1<=N,M<=8),some of them are blocked, others are unblocked. The Farm is located in the lower left plot and the Market is located in the lower right plot. Tony takes her tour of the township going from Farm to Market by walking through every unblocked plot exactly once.
Write a program that will count how many unique tours Betsy can take in going from Farm to Market.
大致：从左下角到右下角的方案数（要求：必须经过所以‘.‘的点）

思路：

首先插头dp的模板题大概是求回路，这里求通路。
因为通常是从上往下，所以可以把整个图翻转，从左上->右上，如果变成回路的话，可以在前面再加一行，这一行的插头情况是，只有最左端和最右端有一个向下的插头，中间都没插头。
这个可以当做初始状态，然后再从第一行开始转移。

//POJ 1739
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
bool cur1;
using namespace std;
void Rd(int &res) {
	res=0;
	char c;
	int fl=1;
	while(c=getchar(),c<48)if(c==‘-‘)fl=-1;
	do res=(res<<1)+(res<<3)+(c^48);
	while(c=getchar(),c>=48);
	res*=fl;
}
#define M 300005
const int Mod=299987;
int n,m,a[15][15],op,cnt[2],ex,ey,pr[1<<20],la[M],to[2][1<<20];
ll inv[15],ans=0,dp[2][M];
char s[15][15];
bool cur2;
void add(int bit,ll v) {
	int u=(bit%Mod)+1;
	for(int i=la[u]; i; i=pr[i])
		if(to[op][i]==bit) {
			dp[op][i]+=v;
			return;
		}
	to[op][++cnt[op]]=bit,pr[cnt[op]]=la[u],la[u]=cnt[op],dp[op][cnt[op]]=v;
}
int main() {
//	printf("%lf\n",(&cur2-&cur1)/1024.0/1024);
	while(~scanf("%d%d",&n,&m)) {
		if(!(n|m))break;
		memset(a,0,sizeof(a));
		int ex,ey;
		for(int i=1; i<=n; i++)scanf("%s",s[i]+1);
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++) {
				a[i][j]=(s[n-i+1][j]==‘.‘);
				if(s[n-i+1][j]==‘.‘)ex=i,ey=j;
			}
//		for(int i=1; i<=n+1; i++,puts(""))
//			for(int j=1; j<=m+1; j++)printf("%d ",a[i][j]);
//		printf("%d %d\n",ex,ey);
		int res=(1<<(2*m+2))-1;
		memset(dp,0,sizeof(dp));
		memset(la,0,sizeof(la));
		op=0,inv[0]=1;
		for(int i=1; i<=m+1; i++)inv[i]=(inv[i-1]<<2);
		cnt[0]=1,to[0][1]=inv[0]+2*inv[m-1],dp[0][1]=1;
		ll ans=0;
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=cnt[op]; j++)to[op][j]<<=2,to[op][j]&=res;
			for(int j=1; j<=m; j++) {
				op^=1,memset(la,0,sizeof(la)),cnt[op]=0;
				for(int k=1; k<=cnt[op^1]; k++) {
					ll v=dp[op^1][k];
					int od=to[op^1][k],b1=(od>>(2*(j-1)))%4,b2=(od>>(2*j))%4;//从第0位往后开始
					if(!a[i][j]) {
						if(!(b1|b2))add(od,v);
					} else if(!(b1|b2)) {
						if(a[i][j+1]&&a[i+1][j])add(od+inv[j-1]+inv[j]*2,v);
					} else if(b1&&(!b2)) {
						if(a[i][j+1])add(od-b1*inv[j-1]+b1*inv[j],v);
						if(a[i+1][j])add(od,v);
					} else if(b2&&(!b1)) {
						if(a[i][j+1])add(od,v);
						if(a[i+1][j])add(od+b2*inv[j-1]-b2*inv[j],v);
					} else if((b1==1)&&(b2==1)) {
						int k1=1;
						for(int l=j+1; l<=m; l++) {
							if(((od>>(l*2))%4)==1)k1++;
							else if(((od>>(l*2))%4)==2)k1--;
							if(!k1) {
								add(od-inv[j-1]-inv[j]-inv[l],v);
								break;
							}
						}
					} else if((b1==2)&&(b2==2)) {
						int k1=1;
						for(int l=j-2; l>=0; l--) {
							if(((od>>(l*2))%4)==1)k1--;
							else if(((od>>(l*2))%4)==2)k1++;
							if(!k1) {
								add(od-inv[j-1]*2-inv[j]*2+inv[l],v);
								break;
							}
						}
					} else if((b1==2)&&(b2==1))add(od-inv[j-1]*2-inv[j],v);
					else if((i==ex)&&(j==ey))ans+=v;
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

【POJ1739】Tony's Tour -插头dp

原文：https://www.cnblogs.com/cly1231/p/12995180.html