C++(g++ 7.5.0) 解法, 执行用时: 31ms, 内存消耗: 3204K, 提交时间: 2022-09-01 23:52:27

#include <bits/stdc++.h>

using namespace std;

int dt[107];
int dp[107][107][107];
vector<int> v, num;

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 2;i <= n + 1;i++) {
        for (int j = 1;j <= m;j++) {
            char ch;
            cin >> ch;
            if (ch == 'H') dt[i] |= 1 << (j - 1);
        }
    }
    for (int i = 0;i < (1 << m);i++) {
        if ((i & (i << 1)) || (i & (i << 2))) continue;
        v.push_back(i);
        num.push_back(__builtin_popcount(i));
    }
    int ans = 0;
    for (int i = 2;i <= n + 1;i++) {
        for (int j = 0;j < v.size();j++) {
            int st1 = v[j];
            if (st1 & dt[i]) continue;
            for (int k = 0;k < v.size();k++) {
                int st2 = v[k];
                if (st2 & dt[i - 1]) continue;
                if (st1 & st2) continue;
                for (int l = 0;l < v.size();l++) {
                    int st3 = v[l];
                    if (st3 & dt[i - 2]) continue;
                    if ((st3 & st1) || (st3 & st2)) continue;
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][l] + num[j]);
                }
                ans = max(ans, dp[i][j][k]);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 284ms, 内存消耗: 884K, 提交时间: 2022-10-03 16:29:08

#include<bits/stdc++.h>
using namespace std;
int N, M;
int main() {
    cin >> N >> M;
    vector<string> G(N);
    for (auto &s: G) cin >> s;
    int sz = 1; for (int i = 0; i < M; i++) sz *= 3;
    vector<int> cur(sz);
    cur[0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0, bs = 1; j < M; j++, bs *= 3) {
            vector<int> nxt(sz);
            for (int s = 0; s < sz; s++) {
                int x = s / bs % 3;
                if (x == 0)  nxt[s] = max(cur[s], cur[s+bs]);
                else if (x == 1) nxt[s] = cur[s+bs];
                else if (x == 2 && G[i][j] == 'P') {
                    if (j >= 1 &&  s/(bs/3)%3 == 2) continue;
                    if (j >= 2 &&  s/(bs/9)%3 == 2) continue;
                    nxt[s] = cur[s-bs-bs] + 1;
                }
            }
            cur = nxt;
        }
    }
    cout  << *max_element(cur.begin(), cur.end()) << endl;
}