对模板打的

#include<bits/stdc++.h>
using namespace std;
int dp[2025][2025][12];
char ch[2025][2025];
int a[2025];
int SUM[2025];
int n, m;
int getsum(int index) {
	int tot = 0;
	while(index) {
		if(index & 1) {
			tot++;
		}
		index /= 2;
	}
	return tot;
}
int main() {
	cin >> n >> m;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<m; ++j) {
			cin >> ch[i][j];
			if(ch[i][j] == 'H') {
				a[i] = a[i] << 1;
				a[i] += 1;
			} else {
				a[i] <<= 1;
			}
		}
	}
	for(int i=0; i<(1<<m); ++i) {
		SUM[i] = getsum(i);
	}
	for(int i=0; i<(1<<m); ++i) {
		if(!((i & a[0]) || (i & (i<<1)) || (i & (i << 2)))) {
			dp[0][i][0] = SUM[i];
		}
	}
	for(int i=0; i<(1<<m); ++i) {
		for(int j=0; j<(1<<m); ++j) {
			if(!(i & j || i & a[0] || j & a[0] || i & (i << 2) || j & (j << 2) || i & (i << 1) || j & (j << 1))) {
				dp[i][j][1] = SUM[i] + SUM[j];
			}
		}
	}
	for(int i=2; i<n; ++i) {
		for(int j=0; j<(1<<m); ++j) {
			if(j&a[i-1] || (j&(j<<1)) || (j&(j<<2))) {
				continue;
			}
			for(int k=0; k<(1<<m); ++k) {
				if(k&a[i] || (k&(k<<1)) || (k&(k<<2)) || k & j) {
					continue;
				}
				for(int l=0; l<(1<<m); ++l) {
					if(l&a[i-2] || (l&(l<<1)) || (l&(l<<2)) || l & k || l & j) {
						continue;
					}
					dp[j][k][i%3]=max(dp[j][k][i%3],dp[l][j][(i-1)%3]+SUM[k]);
				}
			}
		}
	}
	int ans = 0;
	for(int i=0;i<(1<<m);i++)
		for(int j=0;j<(1<<m);j++)
			ans=max(ans,dp[i][j][(n-1)%3]);
	cout << ans;
	return 0;
}