求问玄关

#include <bits/stdc++.h>

using namespace std;

int n,m,can[110][4200],num[110],maxs[110],f[110][2100][2100],ans,cnt[2100];
char a[110][7 + 8];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	
	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 ++)
		for(int j = m;j >= 1;j --)
			if(a[i][j] == 'P') maxs[i] += (1 << (m - j)); 
	for(int i = 1;i <= (1 << 10) + 5;i ++){
		int x = 1;
		while(x <= i){
			if(x & i) cnt[i] ++;
			x <<= 1;
		}
	}
	
	for(int i = 1;i <= n;i ++){
		for(int j = maxs[i];;j = maxs[i] & (j - 1)){
			if(!((j << 2) & j) && !((j << 1) & j)) can[i][++ num[i]] = j;
			if(!j) break;
		}
	}
	
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= num[i];j ++){
			int state = can[i][j];
			if(i == 1){
				f[i][state][0] = max(f[i][state][0],cnt[state]);
				continue;
			}
			for(int k = 1;k <= num[i - 1];k ++){ //枚举上一行
				int lst_state = can[i - 1][k];
				if(i > 1 && (state & lst_state)) continue;
				if(i == 2){
					f[i][state][lst_state] = max(f[i][state][lst_state],cnt[state] + cnt[lst_state]);
					continue;
				}
				for(int o = 1;o <= num[i - 2];o ++){
					int lst_bf_state = can[i - 2][o];
					if(i > 2 && (state & lst_bf_state)) continue;
					if(i > 2 && (lst_state & lst_bf_state)) continue;
					
					f[i][state][lst_state] = max(f[i - 1][lst_state][lst_bf_state] + cnt[state],f[i][state][lst_state]);
				}
			}
		}
	}
	
	for(int i = 0;i <= (1 << 10) + 5;i ++){
		for(int j = 0;j <= (1 << 10) + 5;j ++){
			ans = max(ans,f[n][i][j]);
		}
	}
	
	cout << ans;
}