Description

题目大意:给你个N x M(1≤N, M≤9)的矩阵,0表示空地,1表示墙壁,2和3表示两对关键点。现在要求在两对关键点之间建立两条路径,其中两条路径不可相交或者自交(就是重复经过同一格子),并且不能经过墙壁,路径只能从一个格子走到相邻的下一格子。求两条路径最少需要经过的格子数减二。如果不存在解,输出0。

Solution

插头DP,用三进制来表示轮廓线,0表示没有插头,1表示“2”的的插头,2表示“3”的插头

  1. 对于0的格子:00 -> 00,11,22;01/10 -> 01/10;02/20 -> 02/20;11/22 -> 00。
  2. 对于1的格子:00 -> 00。
  3. 对于2的格子:01/10 -> 00,00 -> 01/10。
  4. 对于3的格子:02/20 -> 00,00 -> 02/20。

但是if太多会超时,所以有必要减少if语句的使用

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 11
using namespace std; const int A[]={1,3,9,27,81,243,729,2187,6561,19683,59049};
int n,m,g[N][N],dp[N][N][59049]; inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
} int main(){
while(~scanf("%d%d",&n,&m)&&n+m){
memset(g,0,sizeof(g));
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)g[i][j]=read(); dp[0][m][0]=0;
for(int i=1;i<=n;++i){
for(int j=0;j<A[m];++j)//A[m]
dp[i][0][j*3]=dp[i-1][m][j];
for(int j=1;j<=m;++j){
for(int k=0;k<A[m+1];++k){//A[m+1]
if (j==m&&k>=A[m]) break;
int a=(k/A[j-1])%3,b=(k/A[j])%3;
if(g[i][j]==1){
if(a==0&&b==0) dp[i][j][k]=dp[i][j-1][k];
}else if(g[i][j]==2){//min,+1
if(a==1&&b==0) dp[i][j][k]=dp[i][j-1][k-A[j-1]]+1;
else if(a==0&&b==1) dp[i][j][k]=dp[i][j-1][k-A[j]]+1;
else if(a==0&&b==0) dp[i][j][k]=min(dp[i][j-1][k+A[j-1]],dp[i][j-1][k+A[j]])+1;
}else if(g[i][j]==3){
if(a==2&&b==0) dp[i][j][k]=dp[i][j-1][k-2*A[j-1]]+1;
else if(a==0&&b==2) dp[i][j][k]=dp[i][j-1][k-2*A[j]]+1;
else if(a==0&&b==0) dp[i][j][k]=min(dp[i][j-1][k+2*A[j-1]],dp[i][j-1][k+2*A[j]])+1;
}
else if(g[i][j]==0){
if(a==0&&b==0) dp[i][j][k]=min(dp[i][j-1][k],min(dp[i][j-1][k+A[j]+A[j-1]]+1,dp[i][j-1][k+2*A[j]+2*A[j-1]]+1));
else if(a==0&&b>0) dp[i][j][k]=min(dp[i][j-1][k],dp[i][j-1][k+b*A[j-1]-b*A[j]])+1;
else if(a>0&&b==0) dp[i][j][k]=min(dp[i][j-1][k],dp[i][j-1][k+a*A[j]-a*A[j-1]])+1;
else if(a&&b&&a==b) dp[i][j][k]=dp[i][j-1][k-a*A[j]-a*A[j-1]]+1;
}
if (i==n&&j==m) break;
}
}
}
if(dp[n][m][0]<0x3f3f3f3f) printf("%d\n",dp[n][m][0]-2);
else printf("0\n");
}
return 0;
}
05-11 22:00