uvalive3620Manhattan Wiring

链接：http://acm.hust.edu.cn/vjudge/problem/11229

题意：给定一个n*m的矩阵，矩阵中有两个2和两个3，其他的为0/1，0表示空地，1表示障碍。要求将2连到2，3连到3并且两条线不能相交，求最短距离。

分析：大白书轮廓线dp例题，用3进制保存状态，枚举所有转移时的状态。注意新的一行开始时要将上一行最后那个点的状态的轮廓线右移一位。

代码：

#include<map> #include<set> #include<cmath> #include<queue> #include<bitset> #include<math.h> #include<vector> #include<string> #include<stdio.h> #include<cstring> #include<iostream> #include<algorithm> #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; const int N=12; const int mod=1000000007; const int MOD1=1000000007; const int MOD2=1000000009; const double EPS=0.00000001; typedef long long ll; const ll MOD=1000000007; const int INF=1000000010; const ll MAX=1000000000; const double pi=acos(-1.0); typedef double db; typedef unsigned long long ull; int t[N],s[N],ma[N][N],dp[2][60000],f[60000][10]; void deal(int n) { int i,j; t[0]=1;s[0]=2; for (i=1;i<N;i++) t[i]=t[i-1]*3,s[i]=t[i]*2; for (i=0;i<n;i++) for (j=0;j<10;j++) f[i][j]=(i/t[j])%3; } int main() { int i,j,k,n,m,mx,now,pre,L,U,news,newt,last; deal(60000); while (scanf("%d%d", &n, &m)&&(n||m)) { for (i=0;i<n;i++) for (j=0;j<m;j++) scanf("%d", &ma[i][j]); now=pre=dp[0][0]=0;mx=t[m+1]-1; for (i=1;i<=mx;i++) dp[0][i]=100; for (i=0;i<n;i++) for (j=0;j<m;j++) { pre=now;now^=1; for (k=0;k<=mx;k++) dp[now][k]=100; for (k=0;k<=mx;k++) if (dp[pre][k]!=100) { if (j==0&&k*3>=t[m+1]) continue ; j==0 ? last=k*3:last=k; L=f[last][j];U=f[last][j+1]; if (ma[i][j]==0) { newt=news=last; if (L==0&&U==0) { newt+=t[j]+t[j+1];news+=s[j]+s[j+1]; dp[now][last]=min(dp[now][last],dp[pre][k]); dp[now][newt]=min(dp[now][newt],dp[pre][k]+1); dp[now][news]=min(dp[now][news],dp[pre][k]+1); } else if (L==0&&U==1) { newt+=t[j]-t[j+1]; dp[now][last]=min(dp[now][last],dp[pre][k]+1); dp[now][newt]=min(dp[now][newt],dp[pre][k]+1); } else if (L==0&&U==2) { news+=s[j]-s[j+1]; dp[now][last]=min(dp[now][last],dp[pre][k]+1); dp[now][news]=min(dp[now][news],dp[pre][k]+1); } else if (L==1&&U==0) { newt+=t[j+1]-t[j]; dp[now][last]=min(dp[now][last],dp[pre][k]+1); dp[now][newt]=min(dp[now][newt],dp[pre][k]+1); } else if (L==1&&U==1) { newt-=t[j]+t[j+1]; dp[now][newt]=min(dp[now][newt],dp[pre][k]+1); } else if (L==2&&U==0) { news+=s[j+1]-s[j]; dp[now][last]=min(dp[now][last],dp[pre][k]+1); dp[now][news]=min(dp[now][news],dp[pre][k]+1); } else if (L==2&&U==2) { news-=s[j]+s[j+1]; dp[now][news]=min(dp[now][news],dp[pre][k]+1); } } else if (ma[i][j]==1) { if (L==0&&U==0) dp[now][last]=min(dp[now][last],dp[pre][k]); } else if (ma[i][j]==2) { if (L==0&&U==0) { dp[now][last+t[j]]=min(dp[now][last+t[j]],dp[pre][k]); dp[now][last+t[j+1]]=min(dp[now][last+t[j+1]],dp[pre][k]); } if (L==1&&U==0) { dp[now][last-t[j]]=min(dp[now][last-t[j]],dp[pre][k]); } if (L==0&&U==1) { dp[now][last-t[j+1]]=min(dp[now][last-t[j+1]],dp[pre][k]); } } else { if (L==0&&U==0) { dp[now][last+s[j]]=min(dp[now][last+s[j]],dp[pre][k]); dp[now][last+s[j+1]]=min(dp[now][last+s[j+1]],dp[pre][k]); } if (L==2&&U==0) { dp[now][last-s[j]]=min(dp[now][last-s[j]],dp[pre][k]); } if (L==0&&U==2) { dp[now][last-s[j+1]]=min(dp[now][last-s[j+1]],dp[pre][k]); } } } } if (dp[now][0]!=100) printf("%d\n", dp[now][0]+2); else printf("0\n"); } return 0; }