jzy_go @ 2020-08-23 10:03:52
#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+(ch-'0');
ch=getchar();
}
return x*f;
}
int n,m;
struct node{
int num;
int a[1001];
}a[1001];
int w[1001][1001];
int f[1001][1001];
void chuli(int x,int y)
{
for(int j=0;j<(1<<m);j++)
{
if((j&(j<<1))||(j&(j>>1))||(j&y)||(j&(j<<2))||(j&(j>>2)))
continue;
a[x].num++;
a[x].a[a[x].num]=j;
}
}
int main()
{
n=read();
m=read();
int x;
char ch;
for(int i=1;i<=n;i++)
{
int y=0;
for(int j=1;j<=m;j++)
{
ch=getchar();
if(ch=='H')
x=0;
else
x=1;
y=y*2+1-x;
}
chuli(i,y);
ch=getchar();
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=a[i].num;j++)
{
int kk=a[i].a[j];
while(kk)
{
if(kk&1)
w[i][j]++;
kk=kk>>1;
}
}
}
for(int j=1;j<=a[2].num;j++)
{
for(int k=1;k<=a[1].num;k++)
{
if(a[2].a[j]&a[1].a[k])
continue;
f[2][j]=max(f[2][j],f[1][k]+w[2][j]);
}
}
for(int i=3;i<=n;i++)
{
for(int j=1;j<=a[i].num;j++)
{
for(int k=1;k<=a[i-1].num;k++)
if(a[i].a[j]&a[i-1].a[k])
continue;
else
for(int o=1;o<=a[i-2].num;o++)
{
if((a[i].a[j]&a[i-2].a[o])||(a[i-1].a[k]&a[i-2].a[o]))
continue;
f[i][j]=max(f[i][j],f[i-1][k]+f[i-2][o]+w[i][j]);
}
}
}
int ans=0;
for(int j=1;j<=a[n].num;j++)
{
ans=max(ans,f[n][j]);
}
cout<<ans<<endl;
return 0;
}