求调

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int h[105];
ll dp[105][1065][1065];

int count(int x){
	int cnt = 0;
	while(x){
		cnt += (x & 1);
		x >>= 1;
	}
	return cnt;
}

signed main(){
	ios:: sync_with_stdio(false);
	vector<int> path;
	int n,m;
	cin>>n>>m;
	for(int i = 0; i < (1 << m); ++i){
		if(i & (i << 1))  continue ;
		if(i & (i << 2))  continue ;
		path.push_back(i);
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < m; j++){
			char ch;
			cin>>ch;
			if(ch == 'H')  h[i] |= 1;
			h[i] <<= 1;
		}
	}
	ll ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < path.size(); j++){
			if(path[j] & h[i])  continue ;
			for(int k = 0; k < path.size(); k++){
				if(path[k] & path[j])  continue ;
				for(int l = 0; l < path.size(); l++){
					if(path[l] & path[j])  continue ;
					dp[i][j][k] = max(dp[i][j][k],dp[i-1][k][l] + count(path[j]));
					ans = max(ans,dp[i][j][k]);
				}
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}