郑厂长系列故事——排兵布阵
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1509 Accepted Submission(s): 554
Problem Description
郑厂长不是正厂长
也不是副厂长
他根本就不是厂长
事实上
他是带兵打仗的团长
也不是副厂长
他根本就不是厂长
事实上
他是带兵打仗的团长
一天，郑厂长带着他的军队来到了一个n*m的平原准备布阵。
根据以往的战斗经验，每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然，一个士兵不能站在另外一个士兵所能攻击到的位置，同时因为地形的原因平原上也不是每一个位置都可以安排士兵。
现在，已知n,m 以及平原阵地的具体地形，请你帮助郑厂长计算该阵地,最多能安排多少个士兵。
Input
输入包含多组测试数据；
每组数据的第一行包含2个整数n和m (n <= 100, m <= 10 )，之间用空格隔开；
接下来的n行，每行m个数，表示n*m的矩形阵地，其中1表示该位置可以安排士兵，0表示该地形不允许安排士兵。
每组数据的第一行包含2个整数n和m (n <= 100, m <= 10 )，之间用空格隔开；
接下来的n行，每行m个数，表示n*m的矩形阵地，其中1表示该位置可以安排士兵，0表示该地形不允许安排士兵。
Output
请为每组数据计算并输出最多能安排的士兵数量，每组数据输出一行。
Sample Input
6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Sample Output
2
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
int a[][],n,m,zh,b[],dp[][][];
bool check(int x,int y)
{
int x1=x<<,x2=x>>;
if(y&x1)return ;
if(y&x2)return ;
return ;
}
bool check1(int x,int y)
{
if(x&y)return ;
return ;
}
bool check2(int x,int y)
{
int z=x|y;
if(z>y)return ;
return ;
}
int fun(int x)
{
int s=;
while(x)
{
s+=x&;
x>>=;
}
return s;
}
void init()
{
zh=;
for(int i=; i<(<<m); i++)
{
if(!(i&(i<<)))
{
a[][zh]=i;
a[][zh++]=fun(i);
}
}
}
int main()
{ while(~scanf("%d%d",&n,&m))
{
init();
int i,j,x,k,r;
memset(dp,,sizeof(dp));
x=getchar();
for(i=; i<n; i++)
{
b[i]=;
for(j=; j<m; j++)
{
x=getchar();
b[i]=(b[i]<<)+x-'';
x=getchar();
}
}
int ix,iy;
for(i=; i<n; i++)
{
ix=i&,iy=!ix;
for(j=; j<zh; j++)
{
if(check2(a[][j],b[i]))
if(!i)
{
dp[][][j]=a[][j];
}
else if(i==)
{
for(k=; k<zh; k++)
{
if(check(a[][k],a[][j]))
dp[][k][j]=dp[][][k]+a[][j];
}
}
else
{
for(k=; k<zh; k++)
{
if(check(a[][k],a[][j]))
{
for(r=; r<zh; r++)
{
if(check1(a[][r],a[][j]))
dp[ix][k][j]=dp[ix][k][j]>dp[iy][r][k]+a[][j]?dp[ix][k][j]:dp[iy][r][k]+a[][j];
}
} }
}
}
}
int sum=;
for(i=; i<zh; i++)
for(j=; j<zh; j++)
sum=sum>dp[ix][i][j]?sum:dp[ix][i][j];//,cout<<dp[1][i][j]<<" ";
printf("%d\n",sum);
}
}