题解 | #小红的扫雷游戏#

分析

非常好的模拟 + 位运算题目

因为棋盘最大是, 如果用二进制表示状态的话最多种状态

因此用二进制表示每个位置是否是雷, 对于初始状态已经有数字的部分自然不是雷

答案应该是初始状态的子集并且每个位置的数字和周围雷的排布情况应该是一样的

因此可以写一个函数判断当前状态是否是合法的, 具体实现看代码

实现代码

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 5, MOD = 998244353;
const LL INF = 1e18;

const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n = 4;
char g[N][N];

bool check(int s) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            char c = g[i][j];
            if (c == '.') continue;
            int cnt = 0;
            for (int k = 0; k < 8; ++k) {
                int nx = i + dx[k], ny = j + dy[k];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                int t = nx * 4 + ny;
                if (s >> t & 1) cnt++;
            }
            if (cnt != g[i][j] - '0') return false;
        }
    }
    return true;
}

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

    int s = (1 << 16) - 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> g[i][j];
            if (g[i][j] != '.') s -= 1 << (i * 4 + j);
        }
    }

    int st[N][N] = {0};
    for (int i = 0; i < 1 << 16; ++i) {
        if ((i | s) == s && check(i)) {
            for (int r = 0; r < n; ++r) {
                for (int c = 0; c < n; ++c) {
                    int t = r * 4 + c;
                    if ((i & 1 << t) == 0) st[r][c] |= 1;
                    else st[r][c] |= 2;
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (st[i][j] == 1) {
                if (g[i][j] == '.') g[i][j] = 'O';
            }
            else if (st[i][j] == 2) g[i][j] = 'X';
            else g[i][j] = '.';
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << g[i][j];
        }
        cout << '\n';
    }

    return 0;
}