题解 | 小红的扫雷游戏

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    char g[4][5];
    for (int i = 0; i < 4; ++i) cin >> g[i];
    vector<pair<int, int>> unk;
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j)
            if (g[i][j] == '.') unk.emplace_back(i, j);
    int U = unk.size();
    struct Clue { int r, c, need; };
    vector<Clue> clues;
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j)
            if (isdigit(g[i][j])) clues.push_back({i, j, g[i][j] - '0'});
    vector<bool> valid(1 << U, true);
    for (int mask = 0; mask < (1 << U); ++mask) {
        for (auto &cl : clues) {
            int cnt = 0;
            for (int dr = -1; dr <= 1; ++dr)
                for (int dc = -1; dc <= 1; ++dc) {
                    if (dr == 0 && dc == 0) continue;
                    int nr = cl.r + dr, nc = cl.c + dc;
                    if (nr < 0 || nr > 3 || nc < 0 || nc > 3) continue;
                    char ch = g[nr][nc];
                    if (ch == 'X') ++cnt;
                    else if (isdigit(ch)) continue;
                    else {
                        auto it = find(unk.begin(), unk.end(), make_pair(nr, nc));
                        int id = it - unk.begin();
                        if (id < U && (mask >> id & 1)) ++cnt;
                    }
                }
            if (cnt != cl.need) { valid[mask] = false; break; }
        }
    }
    vector<char> res;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            res.push_back(g[i][j]);
        }
    }
    for (int id = 0; id < U; ++id) {
        bool all1 = true, all0 = true;
        for (int mask = 0; mask < (1 << U); ++mask) if (valid[mask]) {
            if (mask >> id & 1) all0 = false;
            else                all1 = false;
        }
        auto [r, c] = unk[id];
        if (all1)      res[r * 4 + c] = 'X';
        else if (all0) res[r * 4 + c] = 'O';
    }
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) cout << res[i * 4 + j];
        cout << '\n';
    }
    return 0;
}

// 64 位输出请用 printf("%lld")