```
#include <iostream>
using namespace std;
int n,m;
char a[105][15];
int dp[2050][2050][105];
int hefa[2050],h=1;
int ban[2050];
int one[2050];
int ans=0;
int got(int x){
int t=0;
while(x){
if(x&1){
t++;
}
x>>=1;
}
return t;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='P'){
ban[i]=ban[i]|(1<<j);
}
}
}
for(int f=1;f<(1<<(m+1));f++){
if(f&1==1)continue;
if((((f>>1)|(f<<1)|(f>>2)|(f<<2))&f)==0){
hefa[h]=f;
one[h]=got(f);
if((f&ban[1])==f){
dp[1][f][1]+=one[h];
ans=max(ans,dp[1][f][1]);
}
h++;
}
}
if(n==1){
cout<<ans<<endl;
return 0;
}
if(n>=2){
for(int i=1;i<h;i++){
int f1=hefa[i];
if((f1&ban[2])!=f1)continue;
for(int j=1;j<h;j++){
int f2=hefa[j];
if((i==j) || (f2&ban[1])!=f2)continue;
if((f1&f2)!=0)continue;
dp[f2][f1][2]=max(dp[f2][f1][2],dp[1][f2][1]+one[i]);
ans=max(ans,dp[f2][f1][2]);
}
}
if(n==2){
cout<<ans<<endl;
return 0;
}
}
if(n>2){
for(int mm=3;mm<=n;mm++){
for(int i=1;i<h;i++){
int f1=hefa[i];
if((f1&ban[mm])!=f1)continue;
for(int j=1;j<h;j++){
int f2=hefa[j];
if((i==j) || (f2&ban[mm-1])!=f2)continue;
if((f1&f2)!=0)continue;
for(int k=1;k<h;k++){
int f3=hefa[k];
if((k==j) || (k==i) || (f3&ban[mm-2])!=f3)continue;
if((f3&f2)!=0)continue;
if((f3&f1)!=0)continue;
dp[f2][f1][mm]=max(dp[f2][f1][mm],dp[f3][f2][mm-1]+one[i]);
ans=max(ans,dp[f2][f1][mm]);
}
}
}
}
cout<<ans<<endl;
return 0;
}
}
```
by OutsideR_ @ 2024-04-11 13:24:24