题解：B4167 [GXPC-S 2024] 扫雷

· · 题解

一看题目数据立马就知道这题是暴力。

题意：

给定一个 n 行 m 列的字符矩阵，每个格子可能是三种类型：

问判断是否存在一种方式，将所有 ? 格子确定为有雷或无雷，使得整个棋盘满足所有数字格子的约束条件。

题目分析：

仔细理解题目。

题目的难点在于 ? 格子是未确定的。

由于数据规模很小（n,m≤10，且 ? 的数量不超过 10），其实我们完全可以采用暴力枚举的方法（最多也就 2^{10}=1024 种可能性）。

也就是说，我们可以直接枚举每个 ? 格子是地雷还是安全的两种状态，然后验证整个棋盘是否满足所有约束条件。

对于每个数字格子，我们检查其周围八个格子中的地雷总数是否等于该数字。

题目解答：

我们可以先使用位运算枚举所有可能的状态组合，对于每种组合，将 ? 格子替换为 * 或 o（表示无雷）。

然后再验证整个棋盘的合法性。如果一个格子是数字，则其周围八个格子中 * 的数量与数字相等。

如果存在一种情况使得所有约束都满足，则答案是 YES，否则是 NO。

实现时，我们可以枚举二进制数来表示每个 ? 格子的状态，0 表示安全，1 表示地雷，然后再进行判断。

代码：

#include <bits/stdc++.h>
using namespace std;
// 定义两个15x15的字符数组mp和temp，用于存储原始地图和临时地图，留出边界防止越界
char mp[15][15],temp[15][15];
// T表示测试数据组数，n和m分别表示当前棋盘的行数和列数
int T,n,m;
// 定义8个方向的坐标偏移量，用于检查周围8个格子
// 分别对应左上、上、右上、左、右、左下、下、右下
const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
// 检查当前temp棋盘是否合法的函数
bool check() {
    // 遍历棋盘的每个格子，从(1,1)开始到(n,m)
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // 获取当前格子的字符
            char c = temp[i][j];
            // 如果当前格子是数字0-8
            if (c >= '0' && c <= '8') {
                // 统计周围8个格子中地雷的数量
                int count = 0;
                // 遍历8个方向
                for (int k = 0; k < 8; ++k) {
                    // 计算邻居格子的坐标
                    int ni = i + dx[k];
                    int nj = j + dy[k];
                    // 检查邻居坐标是否在有效范围内
                    if (ni >= 1 && ni <= n && nj >= 1 && nj <= m) 
                        // 如果邻居是地雷，则计数加1
                        if (temp[ni][nj] == '*') 
                            count++;
                }
                // 如果统计的地雷数量与当前数字不符，则棋盘不合法
                if (count != c - '0') 
                    return false;
            }
        }
    }
    // 所有格子都满足条件，棋盘合法
    return true;
}
// 主函数
int main() {
    // 优化输入输出流，提高读取速度
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // 读入测试数据组数
    cin >> T;
    // 处理每组测试数据
    while (T--) {
        // 读入当前棋盘的行数n和列数m
        cin >> n >> m;
        // 逐行读入棋盘数据
        for (int i = 1; i <= n; ++i) {
            string line;
            cin >> line;
            // 将字符串中的每个字符复制到mp数组中，下标从1开始
            for (int j = 1; j <= m; ++j) 
                mp[i][j] = line[j - 1]; 
        }
        // 存储所有问号位置的向量
        vector<pair<int, int> >cnt;
        // 遍历整个棋盘，找出所有问号的位置
        for (int i = 1; i <= n; ++i) 
            for (int j = 1; j <= m; ++j) 
                if (mp[i][j] == '?') 
                    cnt.push_back({i, j});
        // 获取问号的总数
        int sz = cnt.size();
        // 标记是否存在合法方案
        bool flag = false;
        // 枚举所有可能的状态组合（2的sz次方种）
        for (int mask = 0; mask < (1 << sz); ++mask) {
            // 将原始棋盘复制到临时棋盘
            for (int i = 1; i <= n; ++i) 
                for (int j = 1; j <= m; ++j) 
                    temp[i][j] = mp[i][j];
            // 根据当前枚举值设置每个问号的状态
            for (int i = 0; i < sz; i++) {
                int x = cnt[i].first;
                int y = cnt[i].second;
                // 如果mask的第i位为1，则设为地雷
                if (mask & (1 << i)) 
                    temp[x][y] = '*';
                // 否则设为空地
                else 
                    temp[x][y] = 'o'; 
            }
            // 检查当前状态是否合法
            if (check()){
                flag = true;
                break;
            }
        }
        // 输出结果
        if(flag)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    // 程序正常结束
    return 0;
}