https://www.luogu.com.cn/record/166774095

测试样例

测评机读到 # 号。

本地与 IDE 均正确

#include<bits/stdc++.h>
using namespace std;
/*
用ｉ表示当前枚举到第几行，ｊ表示当前行的状态，ｋ表示上一行的状态
*/
int n,m;
const int N=105;
int f[N][70][70],d[N];
int g[70],s,c[250];
void G(int k){
	while(k){
		c[s]++;
		k-=(k&(-k));
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string a;
		cin>>a;
		for(int j=0;j<m;j++) d[i]=(d[i]<<1)+(a[j]=='H');
	}
	g[++s]=0;
	for(int i=1;i<(1<<m);i++){
		if(i&(i<<1)||i&(i<<2)||i&(i>>2)||i&(i>>1)) continue;
		g[++s]=i;
		G(i);
	}
	for(int i=1;i<=s;i++){
		if((g[i]&d[1])==0) f[1][i][0]=c[i];
	}
	for(int i=1;i<=s;i++){
		if((g[i]&d[2])!=0) continue;
		for(int j=1;j<=s;j++){
			if(((g[i]&g[j])==0)&&((g[j]&d[1])==0)) f[2][i][j]=c[i]+c[j];
		}
	}
	for(int i=3;i<=s;i++){
		for(int j=1;j<=s;j++){//当前排
			if((g[j]&d[i])!=0) continue;
			for(int k=1;k<=s;k++) {//上一排
				if(((g[j]&g[k])==0)&&((g[k]&d[i-1])==0)){
					for(int k2=1;k2<=s;k2++){//上2排
						if(((g[j]&g[k2])==0)&&((g[k]&g[k2])==0)&&((g[k2]&d[i-2])==0)){
							f[i][j][k]=max(f[i][j][k],f[i-1][k][k2]+c[j]);
						}
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=s;i++){
		for(int j=1;j<=s;j++){
			ans=max(ans,f[n][i][j]);
		}
	}
	cout<<ans;
	return 0;
}