多组n *m
0不能放1可以放
每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。
#include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #include<map> using namespace std; #define MAXN 1<<10 int z[105][15]; int x[105]; int dp[105][200][200]; //dp[i][j][k] 第i行状态为num[j]第i-1行状态为num[k] 的最大士兵数目 int num[200]; //合法状态 int cn[200]; //对应可以放的人数目 int Count(int a) { int ans=0; while(a>0) { if(a&1) ans++; a=a>>1; } return ans; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&z[i][j]); memset(x,0,sizeof(x)); memset(dp,-1,sizeof(dp)); int cnt=0; int en=1<<m; for(int i=0;i<en;i++) if(((i&(i<<2)))==0) { cn[cnt]=Count(i); num[cnt++]=i; } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) if(!z[i][j]) x[i]|=(1<<j); } for(int i=0;i<cnt;i++) //初始化一下 { if(x[0]&num[i]) continue; dp[0][i][0]=cn[i]; } for(int i=1;i<n;i++) //第一行开始转移 { for(int j=0;j<cnt;j++) //这行的状态 { if(x[i]&num[j]) //这一行和这个状态不能矛盾 continue; for(int k=0;k<cnt;k++) //上一行的状态 { if((num[j]&(num[k]<<1))||(num[j]&(num[k]>>1)))//这一行状态和上一行左 右 continue; for(int k1=0;k1<cnt;k1++) //上面第二行状态 { if(num[j]&num[k1]) //上一行和上上行 continue; if(num[k]&(num[k1]<<1)) continue; if(num[k]&(num[k1]>>1)) continue; if(dp[i-1][k][k1]==-1) continue; dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][k1]+cn[j]); } } } } int ans=0; for(int i=0;i<cnt;i++) for(int j=0;j<cnt;j++) ans=max(dp[n-1][i][j],ans); printf("%d ",ans); } return 0; }