witw @ 2022-01-29 13:53:58
#include<iostream>
#include<math.h>
using namespace std;
const int N=1030;
int n,m,idx;
int sit[105][15];//存储每列,每种情况的二进制表示
char a[105][15];
int f[105][15][15];//存储最大个数
int b[105];//预处理每列情况数
void dfs(int i,int sum,int node){
if(node>m){
if(sum>0)sit[i][++idx]=sum;//坐的位置的情况
return;
}
if(a[i][node]!='P')dfs(i,sum,node+1);
else{
dfs(i,sum+(1<<node),node+3);
dfs(i,sum,node+1);
}
}
int lj(int x,int y){//返回当前情况的行的炮兵的个数
int k=sit[x][y];
int res=0;
while(k){
if(k&1)++res;
k>>=1;
}
return res;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)cin>>a[i][j];
}
for(int i=1;i<=n;++i){
idx=0;
dfs(i,0,1);
b[i]=idx;
}
for(int i=1;i<=b[2];++i){
for(int j=1;j<=b[1];++j){
if(sit[1][i]&sit[2][j])continue;
f[2][i][j]=lj(1,i)+lj(2,j);
}
}
for(int i=3;i<=n;++i){
for(int j=1;j<=b[i];++j){
for(int o=1;o<=b[i-1];++o){
for(int p=1;p<=b[i-2];++p){
if(sit[i][j]&sit[i-1][o])continue;
if(sit[i][j]&sit[i-2][p])continue;
f[i][j][o]=max(f[i][j][o],f[i-1][o][p]+lj(i,j));
}
}
}
}
int res=0;
for(int i=1;i<=b[n];++i){
for(int j=1;j<=b[n-1];++j){
res=max(res,f[n][i][j]);
}
}
cout<<res;
return 0;
}