简易炸弹人(Simple Bomberman) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> row_land(n, 0);
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            char ch;
            cin >> ch;
            if (ch == 'B') row_land[r] |= (1 << c);
        }
    }
    vector<int> valid;
    for (int mask = 0; mask < (1 << m); ++mask) {
        if ((mask & (mask << 1)) == 0 && (mask & (mask << 2)) == 0) {
            valid.push_back(mask);
        }
    }
    int S = valid.size();
    vector<vector<int>> dp(S, vector<int>(S, -1)), ndp(S, vector<int>(S, -1));
    dp[0][0] = 0;
    for (int r = 0; r < n; ++r) {
        for (int i = 0; i < S; ++i) {
            fill(ndp[i].begin(), ndp[i].end(), -1);
        }
        vector<int> gain(S, -1);
        for (int i = 0; i < S; ++i) {
            int mask = valid[i];
            if ((mask & row_land[r]) != mask) continue;
            int g = 0;
            for (int c = 0; c < m; ++c) {
                if ((mask >> c) & 1) {
                    g += 1 + (r > 0 ? 1 : 0) + (r + 1 < n ? 1 : 0) + (c > 0 ? 1 : 0) + (c + 1 < m ? 1 : 0);
                }
            }
            gain[i] = g;
        }
        for (int p1 = 0; p1 < S; ++p1) {
            int m1 = valid[p1];
            int forbid1 = m1 | (m1 << 1) | (m1 >> 1);
            for (int p2 = 0; p2 < S; ++p2) {
                if (dp[p1][p2] < 0) continue;
                int m2 = valid[p2];
                for (int cur = 0; cur < S; ++cur) {
                    if (gain[cur] < 0) continue;
                    int mc = valid[cur];
                    if ((mc & forbid1) == 0 && (mc & m2) == 0) {
                        ndp[cur][p1] = max(ndp[cur][p1], dp[p1][p2] + gain[cur]);
                    }
                }
            }
        }
        dp.swap(ndp);
    }
    int ans = 0;
    for (int i = 0; i < S; ++i) {
        for (int j = 0; j < S; ++j) {
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << "\n";
    return 0;
}