求条

#include<bits/stdc++.h>
using namespace std;
int qk[110],dp[110][(1<<10)];
bool can[110];
int res(int n)
{
	int ans=0;
	while(n)
	{
		ans+=(n%2);
		n/=2;
	}
	return ans;
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			char c;
			cin>>c;
			qk[i]=(qk[i]<<1)+(c=='H');
		}
	for(int i=0;i<(1<<m);i++)
		if(!((i<<1)&i)&&!((i<<2)&i)&&!((i>>1)&i)&&!((i>>2)&i))
		{
			can[i]=1;
			if((i&qk[1])==0)
			{
				dp[1][i]=res(i);
			}
		}
	if(n==1)
	{
		int ans=0;
		for(int i=0;i<(1<<m);i++)ans=max(ans,dp[1][i]);
		cout<<ans;
		return 0;
	}
	for(int qk1=0;qk1<(1<<m);qk1++)
		if(dp[1][qk1])
			for(int qk2=0;qk2<(1<<m);qk2++)
				if(can[qk2]&&(qk1&qk2)==0&&(qk2&qk[2])==0)
				{
					dp[2][qk2]=res(qk2)+dp[1][qk1];
				}
	if(n==2)
	{
		int ans=0;
		for(int i=0;i<(1<<m);i++)ans=max(ans,dp[2][i]);
		cout<<ans;
		return 0;
	}
	for(int i=3;i<=n;i++)
		for(int qk1=0;qk1<(1<<m);qk1++)
			if(can[qk1]&&(qk1&qk[i-2])==0)
				for(int qk2=0;qk2<(1<<m);qk2++)
					if(can[qk2]&&(qk2&qk[i-1])==0&&(qk1&qk2)==0)
						for(int qk3=0;qk3<(1<<m);qk3++)
							if(can[qk3]&&(qk3&qk[i])==0&&(qk1&qk3)==0&&(qk2&qk3)==0)
							{
								dp[i][qk3]=dp[i-1][qk2]+res(qk3); 
							}
	int ans=0;
	for(int i=0;i<(1<<m);i++)
		ans=max(ans,dp[n][i]);
	cout<<ans;
	return 0;
}