题意：曼哈顿距离是指:|x1-x2|+|y1-y2|，只要知道这个概念题意就懂了。
分析：这道题与前面做的几道题有所不同，因为当前行不仅与前一行有关，而且与前两行有关，所以我们开数组的时候还要记录前两行的状态，所以我们需要开设三维数组。
代码实现：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; int n,m,a[];
int dp[][][],st[],num,b[]; int suan(int x)
{
int sum=,i;
for(i=; i<=; i++)
{
if((x&))
sum++;
x=x>>;
}
return sum;
} void chushihua()
{
int i,max=<<;
for(i=; i<max; i++)
if((i&(i<<))==&&(i&(i>>))==)
{
st[num]=i;
b[num++]=suan(i);
}
} void solve()
{
int i,j,k,l,p=,max=<<m,res=,temp;
memset(dp,,sizeof(dp));
if(n>=)
for(i=; i<num&&st[i]<max; i++)
{
if((a[]&st[i])!=st[i])
continue;
temp=b[i];
dp[][][i]=temp;
}
if(n>)
{
p=p^;
for(i=; i<num&&st[i]<max; i++)
{
if((a[]&st[i])!=st[i])
continue;
temp=b[i];
for(j=; j<num&&st[j]<max; j++)
{
if((a[]&st[j])!=st[j])
continue;
if((st[i]&(st[j]<<))!=||(st[i]&(st[j]>>))!=)
continue;
if(dp[][j][i]<dp[][][j]+temp)
dp[][j][i]=dp[][][j]+temp;
}
}
for(i=; i<=n; i++)
{
p=p^;
for(j=; j<num&&st[j]<max; j++)
{
if((a[i]&st[j])!=st[j])
continue;
temp=b[j];
for(k=; k<num&&st[k]<max; k++)
{
if((st[j]&(st[k]<<))!=||(st[j]&(st[k]>>))!=)
continue;
if((a[i-]&st[k])!=st[k])
continue;
for(l=; l<num&&st[l]<max; l++)
{
if((a[i-]&st[l])!=st[l])
continue;
if((st[k]&(st[l]<<))!=||(st[k]&(st[l]>>))!=)
continue;
if((st[l]&st[j])!=)
continue;
if(dp[p][k][j]<dp[-p][l][k]+temp)
dp[p][k][j]=dp[-p][l][k]+temp;
}
}
}
}
}
for(i=; i<num&&st[i]<max; i++)
for(j=; j<num&&st[j]<max; j++)
{
temp=dp[p][i][j];
if(temp>res)
res=temp;
}
printf("%d\n",res);
} int main()
{
int i,j,temp;
num=;
memset(b,,sizeof(b));
chushihua();
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(a,,sizeof(a));
for(i=; i<=n; i++)
{
a[i]=;
for(j=; j<=m; j++)
{
scanf("%d",&temp);
a[i]=(a[i]<<)+temp;
}
}
solve();
}
return ;
}