这虽然是中文题，然而没看懂，不懂的地方，就是在曼哈顿距离这块，网上搜索了一下，写了个程序，是测试曼哈顿距离的。
曼哈顿距离：两点（x1,y1）（x2,y2）的曼哈顿距离为|x1-x2|+|y1-y2|
测试代码：
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
#define fi first
#define se second
#define prN printf("\n")
#define SI(N) scanf("%d",&(N))
#define SII(N,M) scanf("%d%d",&(N),&(M))
#define SIII(N,M,K) scanf("%d%d%d",&(N),&(M),&(K))
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)
#define Rep(i,a,b) for(int i=(a);i<=(b);i++) char tu[60][60];
int a[100][2];
int main()
{
#ifndef ONLINE_JUDGE
// freopen("C:\\Users\\Zmy\\Desktop\\in.txt","r",stdin);
// freopen("C:\\Users\\Zmy\\Desktop\\out.txt","w",stdout);
#endif // ONLINE_JUDGE int i=2,i1=3;
int p=0;
rep(j,6)
rep(j1,6)
{
if (abs(i-j)+abs(i1-j1)==2)
{
printf("%d %d\n",j,j1);
a[p][0]=j;
a[p++][1]=j1;
}
} // i=2,i1=2;
// rep(j,6)
// rep(j1,6)
// {
// if (abs(i-j)+abs(i1-j1)==2)
// {
// printf("%d %d\n",j,j1);
// a[p][0]=j;
// a[p++][1]=j1;
// }
// } cle(tu,'.');
rep(i,p)
{ tu[a[i][0]][a[i][1]]='*';
} rep(i,6)
{
rep(j,6)
{
printf("%c ",tu[i][j]);
}
prN;
} return 0;
}
这是根据测试样例的背景写的，i，i1是所给坐标，最后输出*的地方，就是他对应的曼哈顿距离 （由图可知：曼哈顿距离就是以这个点为中心的菱形）
AC代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 110
#define M 200 using namespace std; int n,m,a[N];
int dp[N][M][M],cnt,num[M],sum[M];
///dp[i][j][k] 表示第i行的j状态 i-1行的k状态 的最优解 bool ok(int x)
{
return (x&(x<<2))||(x&(x<<2));///第x-2个和x+2个位是否有人，
// 有的话就不符合条件
} int getsum(int x) ///1的个数，即放多少个兵
{
int sum=0;
while(x)
{
if(x&1)sum++;
x>>=1;
}
return sum;
} void init()
{
cnt=0;
for(int i=0; i<(1<<m); i++) ///预处理，压缩
{
if(!ok(i))
{
num[cnt]=i;
sum[cnt++]=getsum(i);
}
}
}
////二进制函数
//int two[100];
//void o_two(int n)
//{
// memset(two,0,sizeof(two));
// int p=1;
// while(n)
// {
// two[p++]=n%2;
// n/=2;
// }
// printf("Two:");
// for (int i=12;i>=1;i--)
// {
// if (i%4==0)
// printf(" ");
// printf("%d ",two[i]);
// }puts("");
//}
int main()
{
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\Zmy\\Desktop\\in.txt","r",stdin);
// freopen("C:\\Users\\Zmy\\Desktop\\out.txt","w",stdout);
#endif // ONLINE_JUDGE
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++)
{
int x;
scanf("%d",&x);
if(x)continue;///方便计算，把0存为1
a[i]|=(1<<j);
}
}
// for (int i=0;i<n;i++)
// o_two(a[i]);
init();///初始化了num（情况数组）和sum（个数数组）
memset(dp,0,sizeof dp);
for(int i=0; i<cnt; i++) ///处理第一行
{
if(a[0]&num[i])continue;
dp[0][i][0]=sum[i];
} ///递推，要考虑三行的情况，
for(int i=1; i<n; i++) //第一行
{
for(int j=0; j<cnt; j++)
{
if(a[i]&num[j])continue; ///第一行与原来矩阵有冲突
for(int k=0; k<cnt; k++) ///第二行
{
if(a[i-1]&num[k])continue;
if(((num[k]<<1)&num[j])||((num[k]>>1)&num[j]))continue; //i-1行
int Max=-1;
for(int l=0; l<cnt; l++) ///第三行
{
if(num[j]&num[l])continue;
if(((num[l]<<1)&num[k])||((num[l]>>1)&num[k]))continue;
Max=max(Max,dp[i-1][k][l]);
}
dp[i][j][k]=Max+sum[j];
}
}
}
int Max=-1;
for(int i=0; i<cnt; i++)
for(int j=0; j<cnt; j++)
Max=max(Max,dp[n-1][i][j]);
printf("%d\n",Max);
}
return 0;
}