题目link

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e2 + 10;
const int MAXM = (1<<10) + 10;
int dp[MAXM][MAXM][3],a[MAXN],sum[MAXM];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char x;
			scanf(" %c",&x);
			a[i]<<=1;
			a[i]+=(x=='H'?1:0);
		}
	}
	for(int i=0;i<(1<<m);i++){
		int j=i,tot=0;
		while(j>0){
			if(j&1) tot++;
			j>>=1;
		}
		sum[i]=tot;
	}
	for(int s=0;s<(1<<m);s++){
		if(!(s&a[0]||(s&(s<<1))||(s&(s<<2)))){
			dp[0][s][0]=sum[s];
		}
	}	
	for(int l=0;l<(1<<m);l++){
		for(int s=0;s<(1<<m);s++){
			if(!(l&s||l&a[0]||s&a[1]||(l&(l<<1))||(l&(l<<2))||(s&(s<<1))||(s&(s<<2)))){
				dp[l][s][1]=sum[s]+sum[l];
			}
		}
	}	
	for(int i=2;i<n;i++){
		for(int l=0;l<(1<<m);l++){
			if(l&a[i-1]||(l&(l<<1))||(l&(l<<2))) continue;
			for(int s=0;s<(1<<m);s++){
				if(s&a[i]||l&s||(s&(s<<1))||(s&(s<<2))) continue;
				for(int r=0;r<(1<<m);r++){
					if(r&l||r&s||r&a[i-2]||(r&(r<<1))||(r&(r<<2)))	continue;
					dp[l][s][i%3]=max(dp[l][s][i%3],dp[r][l][(i-1)%3]+sum[s]);
				}
			}
		}
	}
	int ans=0;
	for(int l=0;l<(1<<m);l++){
		for(int s=0;s<(1<<m);s++){
			ans=max(ans,dp[l][s][(n-1)%3]);
		}
	}	
	printf("%d",ans);
	return 0;
}