萌新求助10分

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<10);
const int IM=2147483647;
const long long LLM=9223372036854775807;

inline int read()
{
	int x=0,y=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') y=-y;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^'0');c=getchar();}
	return x*y;
}

int n,m,num,g[N],mp[N],cnt[N],f[3][N][N];
string s;

signed main()
{
	n=read(),m=read();
	
	for(int i=1;i<=n;i++)//初始化存地形 
	{
		cin>>s; 
		for(int j=0;j<m;j++)
		{
			mp[i]<<=1;
			if(s[j]=='H') mp[i]++;
		}
	}
	
	for(int i=0;i<(1<<n);i++)
	{
		int p=i;
		while(p){if(p&1) cnt[i]++;p>>=1;}
		if((!(i&(i<<2)))&&(!(i&(i>>2)))&&(!(i&(i<<1)))&&(!(i&(i>>1)))) g[++num]=i;//存炮兵可能队形 
	}
	
	for(int i=1+1;i<=n+1;i++)//从第二行开始循环
	{
		for(int l=1;l<=num;l++)
		{
			int s1=g[l];
			if(s1&mp[i]) continue;//判断s1在第i行是否可行 
			for(int r=1;r<=num;r++)
			{
				int s2=g[r];
				if((s2&mp[i-1])||(s1&s2)) continue;//判断s2在第i-1行是否可行 以及s1和s2是否冲突 
				for(int k=1;k<=num;k++)
				{
					int s3=g[k];
					if((s3&mp[i-2])||(s1&s3)||(s2&s3)) continue;//同上 
					f[i%3][s1][s2]=max(f[i%3][s1][s2],f[(i-1)%3][s2][s3]+cnt[s1]);//转移 
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=num;i++)
	{
		int s1=g[i];
		for(int j=1;j<=num;j++)
		{
			int s2=g[j];
			if(s1&s2) continue;
			ans=max(ans,f[n%3][s1][s2]);
		}
	}
	printf("%d\n",ans);
	return 0;
}