die码:

#include<bits/stdc++.h>
using namespace std;
char Char;
bool Maps[111],C[2111];
int n,m,f[111][2111][2111];//T UP DOWN
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>Char;
			Maps[i]=Maps[i]*2+(Char=='H');
		}
	}
	for(int i=0;i<=(1<<m)-1;i++){
		for(int j=0;j<m;j++){
			f[1][0][i]+=bool(i&(1<<j));//统计，顺便处理仅以一行的情况
		}
		C[i]=!(i&((i<<1)|(i<<2)|(i>>1)|(i>>2)));//是否可用
	}
	for(int i=0;i<=(1<<m)-1;i++){
		if(C[i]&&(!(Maps[1]&i))){
			for(int j=0;j<=(1<<m)-1;j++){
				if(C[j]&&(!(Maps[2]&j))&&(!(i&j))){
					f[2][i][j]=max(f[2][i][j],f[1][0][i]+f[1][0][j]);//转移（仅有两行）
				}
			}
		}
	}
	for(int t=3;t<=n;t++){
		for(int i=0;i<=(1<<m)-1;i++){
			if(C[i]&&(!(Maps[t-2]&i))){
				for(int j=0;j<=(1<<m)-1;j++){
					if(C[j]&&(!(Maps[t-1]&j))&&(!(i&j))){
						for(int k=0;k<=(1<<m)-1;k++){
							if(C[k]&&(!(Maps[t]&k))&&(!(i&k))&&(!(j&k))){
								f[t][j][k]=max(f[t][j][k],f[t-1][i][j]+f[1][0][k]);//转移（三行及以上）
							}
						}
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<=(1<<m)-1;i++){
		if(C[i]&&(!(Maps[n-1]&i))){
			for(int j=0;j<=(1<<m)-1;j++){
				if(C[j]&&(!(Maps[n]&j))&&(!(i&j))){
					ans=max(ans,f[n][i][j]);//取答案
				}
			}
		}
	}
	cout<<ans;
}

pwp