算法1

(状态压缩DP) $O(3 ^ M * N * (M + 2 ^ k))$

因为只从有效状态扩展，实际上计算量远远小于最坏时间复杂度。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110 , M = 59055;

int n , m;
int p[12] = {0 , 1 , 3 ,  9 , 27 , 81 , 243 , 729 , 2187 , 6561 , 19683,59049};
int f[N][M];
int v[12];
char map[N][12];

void operate(int row ,int last){

    for(int i = 0 ; i < m ; i++ , last /= 3)
      if(last % 3 == 2)v[i + 1] = 1;
      else if(last % 3 == 1)v[i + 1] = 0;
      else if(map[row][i + 1] == 'H')v[i + 1] = 0;
      else v[i + 1] = 2;
}

void dfs(int row ,int col , int last ,int now ,int cnt){

    if(col > m)
    {
        f[row + 1][now] = max(f[row + 1][now] , f[row][last] + cnt);
        return ;
    }

    if(v[col] == 2)
    {
       int v1 = v[col + 1], v2 = v[col + 2];
        if(v[col + 1] == 2)v[col + 1] = 0;
        if(v[col + 2] == 2)v[col + 2] = 0;
        dfs(row , col + 1 , last , now + 2 * p[col], cnt + 1);
        v[col + 1] = v1, v[col + 2] = v2;
    }

    if(v[col] == 1)dfs(row , col + 1 , last,now + p[col] , cnt);

    if(v[col] == 2 || v[col] == 0)dfs(row , col + 1 , last,now , cnt);

}

int main(){

   cin >> n >> m ;

   for (int i = 1; i <= n; i++) scanf("%s", map[i] + 1);

    memset(f , -1 , sizeof(f));
    f[0][0] = 0;
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < p[11] ; j++)
        {
            if(f[i][j] < 0)continue;
            operate(i + 1 , j);
            dfs(i , 1 , j , 0,0);
        }
    }


   int ans = 0;
    for (int j = 0; j < p[11]; j++) ans = max(ans, f[n][j]);
    cout << ans << endl;
    return 0;
}