跟poj 1185 炮兵阵地差不多。
此题由于士兵不能安排在曼哈顿距离为2的地方。
所以只要不是类似：
第i-2行： 010 | 010 | |
第i-1行： 000 | 100 | 001 |
第i行： 010 | | 010 | 1 01
1】同一列隔一行的位置都有士兵。
2】上下行的隔1位有士兵。
3】同一行隔1个的地方有士兵。
dp[i][k][j]和炮兵阵地表示的意义是一样的。第i行的状态为j，第i-1行的状态为k。
转移方程：dp[i][k][j]=max(dp[i][k][j],dp[i-1][t][k]+num[j])。
就可以了。。
啊啊啊啊啊。。。我本来想直接在炮兵阵地的代码上改，不知道哪里粗心，怎么都是wa。。
后来只得重写一遍。。。。所幸这次1a，。。。快吐了。。。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[202][202][202];
int cur[202],ok[202],num[202];
int maxx(int x,int y)
{
return x>y?x:y;
}
int count_1(int x)
{
int sum=0;
while(x)
{
if(x&1)
sum++;
x>>=1;
}
return sum;
}
int main()
{
int n,m,ans,mp;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,-1,sizeof(dp));
memset(cur,0,sizeof(cur));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&mp);
if(mp==0)
cur[i]|=(1<<j);
}
}
int tot=(1<<m);
int cnt=0;
for(int i=0;i<tot;i++)
{
if((i&(i<<2))==0)
{
ok[cnt]=i;
num[cnt++]=count_1(i);
}
}
for(int i=0;i<cnt;i++)
{
if((ok[i]&cur[0])==0)
dp[0][0][i]=num[i];
}
for(int i=1;i<n;i++)
{
for(int j=0;j<cnt;j++)
{
if(cur[i]&ok[j])
continue;
for(int k=0;k<cnt;k++)
{
if(ok[j]&(ok[k]<<1))
continue;
if(ok[j]&(ok[k]>>1))
continue;
for(int t=0;t<cnt;t++)
{
if((ok[t]&ok[j])||(ok[k]&(ok[t]>>1))||(ok[k]&(ok[t]<<1)))
continue;
if(dp[i-1][t][k]==-1)
continue;
dp[i][k][j]=maxx(dp[i][k][j],dp[i-1][t][k]+num[j]);
}
}
}
}
ans=0;
for(int i=0;i<cnt;i++)
{
for(int j=0;j<cnt;j++)
{
if(ans<dp[n-1][i][j])
ans=dp[n-1][i][j];
}
}
printf("%d\n",ans);
}
return 0;
}