Belarus @ 2019-08-23 15:40:25
#include<bits/stdc++.h>
using namespace std;
const int maxn=110,maxm=12;
int n,m,a[maxn][maxm],f[3][(1<<maxm)-1][(1<<maxm)-1],ans;
set<int> s;
set<int>::iterator it;
set<int>::iterator it2;
void statistics(int dep,int status){
if(dep>=m){
s.insert(status);
return;
}
s.insert(status);
for(int i=dep+3;i<m;i++){
s.insert(status);
statistics(i,(status|(1<<i)));
}
}
inline int count(int x){
int cnt=0;
for(int i=m-1;i>=0;i--) if((x>>i)&1) cnt++;
return cnt;
}
inline bool valid(int row,int x){
if(s.find(x)==s.end()) return false;
for(int i=m-1;i>=0;i--) if(((x>>i)&1)&&(!a[row][i])) return false;
return true;
}
int main(){
ios::sync_with_stdio(0);
memset(a,0x3f,sizeof(a));
memset(f,-0x3f,sizeof(f));
cin>>n>>m;
char c;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
c=getchar();a[i][j]=(c=='P')?1:0;
}
s.insert(0);s.insert(1);
for(int i=0;i<m;i++) statistics(i,(1<<i));
f[0][0][0]=0;
for(int i=1;i<n;i++)
for(int j=0;j<(1<<m);j++)
if(valid(i,j))
for(int k=0;k<(1<<m);k++)
if(valid(i-1,k) && k&j==0)
for(int l=0;l<(1<<m);l++)
if(j&l==0) f[i%3][j][k]=max(f[i%3][j][k],f[(i-1)%3][k][l]+count(j));
for(it=s.begin();it!=s.end();it++)
for(it2=s.begin();it2!=s.end();it2++)
ans=max(ans,f[n-1][*it][*it2]);
cout<<ans;
}