本文共 1125 字，大约阅读时间需要 3 分钟。

类似于poj-1185

//曼哈顿距离 d = |x1 - x2| + |y1 - y2|//解决曼哈顿距离冲突 s[i]&(s[j] << 1)||s[i]&(s[j] >> 1)#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int n,m,num;int s[200],p[200],a[200];int dp[110][222][222];bool ok(int x){    if(x&(x<<2)) return false;    return true;}void init(){    num = 0;    for(int i = 0;i < (1<
       
        >1))) return false;    return true;}int main(){    int temp;    while(~scanf("%d%d",&n,&m)){        memset(a,0,sizeof(a));        for(int i = 0;i < n;i++){            for(int j = 0;j < m;j++){                scanf("%d",&temp);                if(!temp) a[i] += (1<
        
         < num;i++){ p[i] = cal(s[i]); if(find(s[i],a[0])) dp[0][i][0] = p[i]; } for(int i = 1;i < n;i++){ for(int j = 0;j < num;j++){ if(s[j]&a[i]) continue; for(int k = 0;k < num;k++){ if(!find1(s[j],s[k])) continue; for(int l = 0;l < num;l++){ if(s[l]&s[j]) continue; if(!find1(s[j],s[k])) continue; dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][l] + p[j]); } } } } int ans = 0; for(int i = 0;i < num;i++){ for(int j = 0;j < num;j++){ ans = max(ans,dp[n-1][i][j]); } } printf("%d\n",ans); }}
        
       
      
     
    
   

转载地址：http://udsgi.baihongyu.com/