求助（20pts）

#include <bits/stdc++.h>
using namespace std;
struct node{
	int num,a[55],king;
	node()
	{
		num=king=0;
	}
}line[105];
int n,m,ans=0;
char mp[15];

void prepare()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<(1<<m);j++)
		{
			if((j&j<<1) || (j&j<<2) || ((j&line[i].king)>0)) continue;
			line[i].num++;
			line[i].a[line[i].num]=j;
		}
	}
	return;
}

int get1(int x)
{
	int res=0;
	while(x)
	{
		if(x&1) res++;
		x>>=1;
	}
	return res;
}

int f[105][1<<4][1<<4];
void dp()
{
	memset(f,0,sizeof(f));
	for(int i=1;i<=line[1].num;i++)
		f[1][line[1].a[i]][0]=get1(line[1].a[i]);
	for(int i=1;i<=line[2].num;i++)
	{
		for(int j=1;j<=line[1].num;j++)
		{
			if(line[2].a[i]&line[1].a[j]) continue;
			f[2][line[2].a[j]][line[1].a[i]]=get1(line[2].a[j])+f[1][line[1].a[i]][0];
		}
	}
	for(int i=3;i<=n;i++)
	{
		//cout<<"*"<<i<<"*"<<endl;
		for(int j=1;j<=line[i].num;j++)
		{
			for(int k=1;k<=line[i-1].num;k++)
			{
				for(int q=1;q<=line[i-2].num;q++)
				{
					if((line[i-1].a[k]&line[i].a[j])||((line[i-2].a[q]&line[i].a[j]))||(line[i-1].a[k]&line[i-2].a[q]))
						continue;
					//cout<<line[i].a[j]<<" "<<line[i-1].a[k]<<" "<<line[i-2].a[q]<<endl;
					f[i][line[i].a[j]][line[i-1].a[k]]=max(f[i][line[i].a[j]][line[i-1].a[k]],f[i-1][line[i-1].a[k]][line[i-2].a[q]]+get1(line[i].a[j]));
				}
			}
		}
	}
	for(int k=1;k<=line[n].num;k++)
	{
		for(int q=1;q<=line[n-1].num;q++)
		{
			ans=max(ans,f[n][line[n].a[k]][line[n-1].a[q]]);
		}
	}
	return;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",mp+1);
		for(int j=1;j<=m;j++)
			if(mp[j]=='H') line[i].king=line[i].king|(1<<(j-1));
	}
	prepare();
	dp();
	cout<<ans;
	/*for(int i=1;i<=n;i++)
	{
		cout<<i<<" "<<line[i].king<<endl;
		for(int j=1;j<=line[i].num;j++) cout<<line[i].a[j]<<" ";
		cout<<endl;
	}*/
    return 0;
}