状压DP，用 $dp[i][j][k]$ 表示前一行状态为 $i$ ，当前行状态为 $j$，当前处于 $k$ 行时对应的最大放置数。

#include<iostream>
#include<cstdio>
#define MAXN (1<<10)
using namespace std;
// f[i][j][k] 表示上一行状态为 i，这一行状态为 j，当前行为第 k 行时可以放的最多的个数
char x;int n,m,a[105],s[MAXN],f[MAXN][MAXN][3],res;
int getsum(int s){int res=0;while(s){s=s&(s-1);res++;}return res;
}
int main(){
#ifdef WINEfreopen("data.in","r",stdin);
#endifscanf("%d%d",&n,&m);for(int i=0;i<n;i++)for(int j=0;j<m;j++){scanf(" %c ",&x);a[i]<<=1;a[i]+=(x=='H'?1:0);}for(int i=0;i<(1<<m);i++)s[i]=getsum(i); // 计算状态中 1 的个数for(int k=0;k<(1<<m);k++) // 计算第 0 行，要求不能放到山丘，并且左右两个内不能重复放置if(!((k&a[0])||(k&(k<<1))||(k&(k<<2))))f[0][k][0]=s[k];for(int i=0;i<(1<<m);i++) // 计算第 1 行for(int j=0;j<(1<<m);j++)if(!(i&j||i&a[0]||j&a[1]||i&(i<<1)||i&(i<<2)||j&(j<<1)||j&(j<<2)))f[i][j][1]=s[i]+s[j];for(int k=2;k<n;k++) // 计算第 2 到 n-1 行for(int i=0;i<(1<<m);i++){if(i&a[k-1]||i&(i<<1)||i&(i<<2))continue; // 不能放到山丘且左右不能重复放置for(int j=0;j<(1<<m);j++){if(j&a[k]||i&j||j&(j<<1)||j&(j<<2))continue;for(int d=0;d<(1<<m);d++){if(d&i||d&j||d&a[k-2]||d&(d<<1)||d&(d<<2))continue; // 不能和前两行有重（纵向）f[i][j][k%3]=max(f[i][j][k%3],f[d][i][(k-1)%3]+s[j]);}}}for(int i=0;i<(1<<m);i++)for(int j=0;j<(1<<m);j++)res=max(res,f[i][j][(n-1)%3]); // 最后一行printf("%d\n",res);return 0;
}