题目链接：[NOI2001] 炮兵阵地 - 洛谷 

思路：类似“互不侵犯”那道题，只不过影响范围变大了，还有加入的地形影响。所以用了类似的写法，但是不知道为什么wa了，debug了好久也没修好，先放着吧。

#include <bits/stdc++.h>
using namespace std;
int n, m, bit[10], cnt[10], size;
int f[100][1<<10][1<<10]; //行数，上一行，当前行
bool mp[100][10]; int g[100];
inline int read(){
	int x=0;char ch=getchar();
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x;
}
void dfs(int b,int c,int pos){ //预处理一行的情况
    if(pos>=m) {bit[++size]=b; cnt[size]=c; return;}
    dfs(b,c,pos+1);
    dfs(b+(1<<pos),c+1,pos+3);
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    n=read(); m=read();
    dfs(0,0,0); //预处理

	//1.处理地图
	char ch;
    for(int i=0; i<n; i++)
	for(int j=0; j<m; j++){
		cin>>ch;
        g[i] = (g[i]<<1)+(ch=='H');
	}

    //补充：n=1的特判
    if(n==1){
        int ans = 0;
        for(int i=1; i<=size; i++){
            if(bit[i]&g[0]) continue;
            ans = max(ans, cnt[i]);
        }
        cout<<ans;
        return 0;
    }

	//2.初始化前两行
    for(int i=1; i<=size; i++)
    for(int j=1; j<=size; j++){
        if((g[0]&bit[i]) || (g[1]&bit[j]) || (bit[i]&bit[j])) continue;
        f[1][bit[i]][bit[j]] = cnt[i]+cnt[j];
    }

	//3.状压dp
	for(int t=2; t<n; t++) //next层数
	for(int i=1; i<=size; i++) //prev
	for(int j=1; j<=size; j++) //cur
	for(int k=1; k<=size; k++){ //next
		if((bit[i]&bit[k]) || (bit[j]&bit[k]) || (bit[k]&g[t])) continue;
		f[t][j][k] = max(f[t][j][k], f[t-1][i][j]+cnt[k]);
	}

	//4.收集答案
	int ans = 0;
	for(int i=1; i<=size; i++)
	for(int j=1; j<=size; j++)
		ans = max(ans, f[n-1][i][j]);
	cout<<ans<<'\n';
}