george0929 @ 2023-11-08 15:31:59
```cpp
#include<bits/stdc++.h>
using namespace std;
int N,M,ful;
int mp[105][15];
int f[105][90][90];
int getc(int sta,int i){
int res=0;
for(int j=1;j<=M;j++){
if(sta&1){
res+=mp[i][j];
}
sta>>=1;
}
return res;
}
int sta[90];
void init(){
for(int i=0;i<(1<<M);i++){
if(i&(i<<2)) continue;
if(i&(i>>2)) continue;
if(i&(i<<1)) continue;
if(i&(i>>1)) continue;
sta[++ful]=i;
}
}
int main(){
cin>>N>>M;
init();
for(int i=1;i<=N;i++){
string s;
cin>>s;
for(int j=0;j<M;j++){
mp[i][j+1]=s[j]=='P'?1:0;
}
}
int ans=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=ful;j++){//第i行
for(int k=1;k<=ful;k++){//第i-1行
if(i==1){
f[i][j][k]=getc(sta[j],i);
ans=max(ans,f[i][j][k]);
continue;
}
if(sta[j]&sta[k]) continue;
int res=0;
for(int p=1;p<=ful;p++){//第i-2行
if(sta[j]&sta[p]) continue;
if(sta[i]&sta[p]) continue;
res=max(res,f[i-1][k][p]);
}
f[i][j][k]=res+getc(sta[j],i);
ans=max(ans,f[i][j][k]);
}
}
}
cout<<ans<<endl;
return 0;
}
```