fjn同款题解

#include<bits/stdc++.h>
using namespace std;
int n,m,g[105],dp[2][105][105];
vector<int>a,cnt;
bool check(int x){
    for(int i=0;i<m;i++){
        if((x>>i)&1&&(((x>>(i+1))&1)||((x>>(i+2))&1))){
            return 0;
        }
    }
    return 1;
}
int count(int x){
    int ans=0;
    for(int i=0;i<m;i++){
        if((x>>i)&1){
            ans++;
        }
    }
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=m-1;j>=0;j--){
            char c; cin>>c;
            if(c=='H')g[i]+=1<<j;
        }
    }
    for(int i=0;i<1<<m;i++){
        if(check(i)){
            a.push_back(i);
            cnt.push_back(count(i));
        }
    }
    for(int i=1;i<=n+2;i++){
        for(int j=0;j<a.size();j++){
            for(int k=0;k<a.size();k++){
                for(int u=0;u<a.size();u++){
                    int a1=a[j],b=a[k],c=a[u];
                    if(a1&b||b&c||a1&c)continue;
                    if(c&g[i]||b&g[i-1])continue;
                    dp[i&1][k][u]=max(dp[i&1][k][u],dp[(i-1)&1][j][k]+cnt[u]);
                }
            }
        }
    }
    cout<<dp[(n+2)&1][0][0]<<endl;
    return 0;
}