题目:
司令部的将军们打算在 N×MN×M 的网格地图上部署他们的炮兵部队。
一个 N×MN×M 的地图由 NN 行 MM 列组成,地图的每一格可能是山地(用 H
表示),也可能是平原(用 P
表示),如下图。
在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示:
如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。
图上其它白色网格均攻击不到。
从图上可见炮兵的攻击范围不受地形的影响。
现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入格式
第一行包含两个由空格分割开的正整数,分别表示 NN 和 MM;
接下来的 NN 行,每一行含有连续的 MM 个字符(P
或者 H
),中间没有空格。按顺序表示地图中每一行的数据。
输出格式
仅一行,包含一个整数 KK,表示最多能摆放的炮兵部队的数量。
数据范围
N≤100,M≤10N≤100,M≤10
输入样例:
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
输出样例:
6
代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N=110,M=1<<12,mod=1e9;
int g[N];//
int dp[2][M][M];//dp[i][j][k]表示第i行为j状态时,第i-1行为k状态时的方案数
int n,m;
int cnt[M];//状态为i时,1的个数
vector <int> a[M];//a[i]表示该行状态为i时,上一行可能的情况
vector <int> a1;//表示符合炮兵阵地左右两边空两个的状态
int count1(int s)
{
int res = 0;
for(int i = 0;i < m;i ++)
if((s >> i & 1) == 1)
res ++;
return res;
}
int main()
{
cin>>n>>m;
string b;
int c;
for(int i=0;i<n;i++)
{
cin>>b;
for(int j=0;j<m;j++)
{
if(b[j]=='P')
c=1;
else
c=0;
g[i]=(g[i]<<1)+c;
}
//cout<<g[i]<<' ';
}
for(int i=0;i<1<<m;i++)//该列状态为j时,上一列存在的状态
for(int j=0;j<1<<m;j++)
{
if(!(i&j))
a[i].push_back(j);
}
for(int i=0;i<(1<<m);i++)
{
if(((i&(i<<1))==0)&&((i&(i>>1))==0&&(i&(i<<2))==0)&&((i&(i>>2))==0))
{
a1.push_back(i);
cnt[i]=count1(i);
}
}
for(int i=1;i<=n+2;i++)
{
for(int j=0;j<a1.size();j++)
{
//if((i==n+2)&&(j>0)) break;//第i+2行只用到状态为0的情况,因为没有i+1行。
int temp3=a1[j];
if((temp3&g[i-1])==temp3)
for(int k=0;k<a[temp3].size();k++)//上一列
{
int temp1=a[temp3][k];
for(int l=0;l<a[temp1].size();l++)//上上一列
{
if((temp3&a[temp1][l])==0)
{
int temp2=a[temp1][l];
//cout<<"j:"<<j<<" ";
int temp=dp[(i-1)&1][temp1][temp2]+cnt[temp3];
//cout<<cnt[j]<<"yy ";
dp[i&1][temp3][temp1]=max(dp[i&1][temp3][temp1],temp);
//cout<<dp[i&1][j][k]<<' ';
}
}
}
}
}
cout<<dp[(n+2)&1][0][0];
return 0;
}