记录

#include<bits/stdc++.h>
using namespace std;
int n,m,b[10005],cnt,start[100005],gx[100005],f[105][105][105],ans;
char a[10005];
int maz[105][105];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",a+1);
		for(int j=1;j<=m;j++)
		{
			if(a[j]=='H') maz[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			b[i]=(b[i]<<1)+maz[i][j];
		}
	}
	start[++cnt]=0;
	for(int i=1;i<(1<<m);i++)
	{
		if(i&(i<<1)) continue;
		if(i&(i<<2)) continue;
		if(i&(i>>1)) continue;
		if(i&(i>>2)) continue;
		start[++cnt]=i;
		int x=i;
		while(x!=0)
		{
			gx[cnt]+=x&1;	
			x=x>>1;
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		if((start[i]&b[1])==0) f[1][i][0]=gx[i];
	}
	for(int i=1;i<=cnt;i++)
	{
		if((start[i]&b[2])==0)
		{
			for(int j=1;j<=cnt;j++)
			{
				if((start[i]&start[j])==0&&(start[j]&b[1])==0)
				{
					f[2][i][j]=gx[i]+gx[j];
				}
			} 
		}
	}
	for(int i=3;i<=n;i++)
	{
		for(int j=1;j<=cnt;j++)
		{
			if((start[j]&b[i])==0)
			{
				for(int k1=1;k1<=cnt;k1++)
				{
					if((start[k1]&start[j])==0&&(start[k1]&b[i-1])==0)
					{
						for(int k2=1;k2<=cnt;k2++)
						{
							if((start[k2]&start[k1])==0&&(start[k2]&start[j])==0&&(start[k2]&b[i-2])==0)
							{
								f[i][j][k1]=max(f[i][j][k1],f[i-1][k1][k2]+gx[j]);
							}
						}
					}
				}
			}
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		for(int j=1;j<=cnt;j++)
		{
			ans=max(ans,f[n][i][j]);
		}
	}
	printf("%d",ans);
	return 0;
}