题解 | 小红的扫雷游戏

枚举每一种解，检查是否符合条件即可。

解最多只有 2¹⁶=65536 种，检查也只需要检查 16 个格子每个周围至多 9 个格子，效率完全可以接受。

#include <bitset>
#include <iostream>
#include <array>
using namespace std;

int Cnt(int x, int y, int cur) {
    int res = 0;
    for (int i = max(0, x - 1); i < min(4, x + 2); i++) {
        for (int j = max(0, y - 1); j < min(4, y + 2); j++) {
            res += (cur >> (i * 4 + j)) & 1;
        }
    }
    return res;
}

array<string, 4> grid;

array<bitset<4>, 4> canBeLei;
array<bitset<4>, 4> canBeEmpty;

bool Check(int x, int y, int cur) {
    return grid[x][y] == '.' || (!((cur >> (x * 4 + y)) & 1) && Cnt(x, y, cur) == grid[x][y] - '0');
}

bool Check(int cur) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (!Check(i, j, cur)) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 0; i < 4; i++) {
        cin >> grid[i];
    }
    for (int i = 0; i < 1 << 16; i++) {
        if (Check(i)) {
            // cout << i << endl;
            for (int x = 0; x < 4; x++) {
                for (int y = 0; y < 4; y++) {
                    if ((i >> (x * 4 + y)) & 1) {
                        canBeLei[x][y] = true;
                    }
                    else {
                        canBeEmpty[x][y] = true;
                    }
                }
            }
        }
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (grid[i][j] == '.') {
                if(!canBeEmpty[i][j]) {
                    grid[i][j] = 'X';
                    continue;
                }
                if (!canBeLei[i][j]) {
                    grid[i][j] = 'O';
                }
            }
        }
    }
    for (const auto& s : grid) {
        cout << s << '\n';
    }
    return 0;
}
// 64 位输出请用 printf("%lld")