啷里个浪 @ 2021-03-04 16:22:23
#include<bits/stdc++.h>
using namespace std;
int n,m,mapi[110],con[1<<11],js[1<<11],f[1<<11][1<<11][110],cnt;
int lowbiti(int x){
int tot=0;
while(x){
if(x&1)++tot;
x=x>>1;
}
return tot;
}
int main(){
char ch;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>ch;
mapi[i]=(mapi[i]<<1)+(ch=='H'?1:0);
}
}
for(int i=0;i<(1<<m);i++){
if((i&(i<<1))==0&&(i&(i<<2))==0&&(i&(i>>1))==0&&(i&(i>>2))==0){
++cnt;
con[cnt]=i;
js[cnt]=lowbiti(i);
}
}
for(int i=1;i<=cnt;i++){
if((mapi[1]&con[i])==0){
f[0][i][1]=js[i];
}
}
for(int i=1;i<=cnt;i++){
if((mapi[2]&con[i])==0){
for(int j=1;j<=cnt;j++){
if((mapi[1]&mapi[j])==0&&(con[i]&con[j])==0)
f[j][i][2]=js[i]+js[j];
}
}
}
for(int i=3;i<=n;i++){//i
for(int j=1;j<=cnt;j++){//the condition of i line
if((mapi[i]&con[j])==0){
for(int k=1;k<=cnt;k++){//the condition of i-1 line
if((mapi[i-1]&con[k])==0&&(con[j]&con[k])==0){
for(int l=1;l<=cnt;l++){//the condition of l-2 line
if((mapi[i-2]&con[l])==0&&(con[l]&con[k])==0&&(con[j]&con[l])==0)
f[k][j][i]=max(f[k][j][i],f[l][k][i-1]+js[j]);
}
}
}
}
}
}
int ans=0;
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++){
ans=max(ans,f[i][j][n]);
}
}
cout<<ans;
return 0;
}