#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
long long n,m,maxx=-1,ans;
long long a[110],dp[110][1100][1010],s[110],num[110];
long long lowbit(long long x){
	return x&-x;
}
long long count(long long x){
	long long cnt=0;
	while(x>0){
		x-=lowbit(x);
		cnt++;
	}
	return cnt;
}
void INIT(){
	for(long long i=0;i<=(1<<m)-1;i++){
		if(!(i&(i<<1))&&!(i&(i<<2))){
			s[ans++]=i;
			num[i]=count(i);
		}
	}
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=n;i++){
		for(long long j=0;j<m;j++){
			char c;
			cin>>c;
			if(c=='P') a[i]+=1<<(m-j-1);
		}
	}
	INIT();
 	for(long long i=1;i<=n;i++){ÐÐ
		for(long long x=0;x<ans;x++){ÐÐ
			for(long long y=0;y<ans;y++){Ð
				for(long long z=0;z<ans;z++){
					if(!(s[x]&s[y])&&!(s[y]&s[z])&&!(s[z]&s[x])&&((a[i]&s[x])==s[x])&&((a[i-1]&s[y])==s[y])){
						dp[i][x][y]=max(dp[i][x][y],dp[i-1][y][z]+num[s[i]]);
					}
				}
			}
		}
	}
	for(long long x=0;x<ans;x++){
		for(long long y=0;y<ans;y++){
			maxx=max(maxx,dp[n][x][y]);
		}
	}
	printf("%lld",maxx);
	return 0;
}

上一次尝试还是在 2024-05-30 17:08:55