求调，必关

记录

#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;
}