题解 | 小红的扫雷游戏

观察矩阵只有4*4，每个点两种放法，故一共2^16方案，即二进制枚举所以方案判断这个点放'O'还是'X'，都行就是'.'

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

int dir[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, -1}, {1, 1}, {-1, 1}, {-1, -1}};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n = 4;
    vector<vector<char>> v(n + 1, vector<char>(n + 1));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cin >> v[i][j];
    }

    vector<vector<char>> e(n + 1, vector<char>(n + 1));

    auto is_no = [&](int x, int y){
        int sum = 0, tag = v[x][y] - '0';
        for (int i = 0; i < 8; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if (dx < 1 || dx > n || dy < 1 || dy > n || v[dx][dy] != '.') continue;
            if (e[dx][dy] == 'X') sum++;
        }
        if (sum == tag) return 1;
        else return 0;
    };

    auto check = [&]() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (v[i][j] != '.') {
                    int f = is_no(i, j);
                    if (f == 0) return 0;
                }
            }
        }
        return 1;
    };

    vector<vector<int>> vis1(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> vis2(n + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < (1ll << 16); i++) {
        string res = "";
        for (int j = 0; j < 16; j++) {
            if (i & (1 << j)) res += 'O';
            else res += 'X';
        }
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= n; y++) {
                e[x][y] = res[(x - 1) * 4 + y - 1];
            }
        }
        if (check()) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (v[i][j] != '.') continue;
                    if (e[i][j] == 'X') vis1[i][j] = 1;
                    if (e[i][j] == 'O') vis2[i][j] = 1;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (v[i][j] != '.') {
                cout << v[i][j];
                continue;
            }
            if (vis1[i][j] && vis2[i][j]) {
                cout << '.';
                continue;
            }
            if (vis1[i][j]) cout << 'X';
            if (vis2[i][j]) cout << 'O';
        }
        cout << "\n";
    }

    return 0;
}