题解 | 小红的扫雷游戏

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using PII=pair<ll,ll>;

// 定义8个方向的行/列偏移量（覆盖右、左、下、右下、左下、上、右上、左上）
// dx对应行偏移，dy对应列偏移，一一配对构成8个方向
ll dx[]={0,0,1,1,1,-1,-1,-1};
ll dy[]={1,-1,0,1,-1,0,1,-1};

char ans[4][4]; // 最终结果数组：存储4x4网格中每个格子的确定状态（数字/X/O/.）
                // X=确定是雷，O=确定不是雷，.=无法确定，数字=原始数字格子

int main(){
    // 关闭输入输出同步，加速cin/cout（优化效率，不影响核心逻辑）
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
    vector<string>a(4); // 存储输入的4x4扫雷网格（0-based索引，行/列均为0-3）
    // q：存储所有数字格子的约束信息
    // 每个元素是unordered_map<ll, unordered_set<ll>>，格式为{数字值: 周围空白格的一维位置集合}
    // 例如：数字3对应周围3个雷，则map中key=3，value是这3个雷所在的空白格位置集合
    vector<unordered_map<ll,unordered_set<ll>>>q;
    unordered_set<ll>s; // 存储所有需要判断的空白格的一维位置（范围0-15，对应4x4网格的16个格子）
    
    // 输入4行扫雷网格数据
    cin>>a[0]>>a[1]>>a[2]>>a[3];
    
    // ====================== 步骤1：收集数字格子的约束 ======================
    // 遍历4x4网格的每个格子（行i：0-3，列j：0-3，均为0-based）
    for(ll i=0;i<4;i++){          
        for(ll j=0;j<4;j++){      
            if(a[i][j]!='.'){    // 找到非空白格（即数字格子）
                // 存储当前数字格子的约束：key=数字值，value=周围空白格的一维位置集合
                unordered_map<ll,unordered_set<ll>>m; 
                
                // 遍历8个方向，查找当前数字格子周围的空白格
                for(ll k=0;k<8;k++){
                    // 计算偏移后的行xt、列yt（均为0-based）
                    ll xt=i+dx[k],yt=j+dy[k]; 
                    
                    // 过滤无效位置：1.坐标超出4x4网格范围 2.偏移后位置不是空白格
                    if(xt<0||xt>3||yt<0||yt>3||a[xt][yt]!='.')continue;
                    
                    // 计算空白格的一维位置（行号*4 + 列号，范围0-15）
                    ll pos = xt*4 + yt;
                    // 记录约束：当前数字值 对应 该空白格位置
                    m[a[i][j]-'0'].insert(pos);
                    // 标记该空白格为需要判断的格子
                    s.insert(pos); 
                }
                
                // 将当前数字格子的约束加入总约束列表
                q.emplace_back(m); 
            }
        }
    }

    // ====================== 步骤2：枚举所有可能的雷分布 ======================
    // 用16位二进制掩码表示雷分布：每一位对应一个格子（0-15），1=该格子是雷，0=不是雷
    // 枚举范围0 ~ (1<<16)-1，覆盖16个格子的所有雷/非雷组合（共65536种可能）
    for(ll i=0;i<=(1<<16)-1;i++){
        ll flag=0; // 标记当前掩码是否合法（0=合法，1=不合法）
        
        // ====================== 步骤3：验证掩码合法性 ======================
        // 遍历所有数字格子的约束，检查当前掩码是否满足所有约束
        for(auto j:q){ // j：单个数字格子的约束（map<数字值, 空白格集合>）
            for(auto [k,v]:j){ // k=数字值（需要的雷数），v=周围空白格的一维位置集合
                ll cnt=0; // 统计当前掩码下，该数字周围的雷的数量
                
                // 遍历该数字周围的所有空白格，统计雷数
                for(auto t:v){ // t：空白格的一维位置
                    if((i>>t)&1){ // 掩码的第t位为1 → 该位置是雷，计数+1
                        cnt++;
                    }
                }
                
                // 若统计的雷数≠数字值 → 掩码不合法，标记后跳出循环
                if(cnt!=k){ 
                    flag=1;
                    break;
                }
            }
            if(flag==1)break; // 只要有一个约束不满足，无需继续检查，跳过当前掩码
        }

        // ====================== 步骤4：更新合法掩码对应的结果 ======================
        // 若当前掩码合法（满足所有数字约束），统计该掩码下空白格的状态
        if(flag==0){
            // 遍历16个格子（一维位置j：0-15）
            for(ll j=0;j<16;j++){ 
                // 将一维位置转换为二维坐标（行it：0-3，列jt：0-3）
                ll it=j/4,jt=j%4; 
                
                // 情况1：原格子是数字 → 直接保留到结果数组
                if(a[it][jt]!='.'){
                    ans[it][jt] = a[it][jt];
                }
                // 情况2：原格子是需要判断的空白格（在集合s中）
                else if(s.find(j)!=s.end()){
                    if((i>>j)&1){ // 当前掩码下该位置是雷（X）
                        // 逻辑：若结果未标记为O/初始态 → 标记为X；否则标记为.（状态冲突，无法确定）
                        if(ans[it][jt]!='O' && ans[it][jt]!='.'){
                            ans[it][jt] = 'X';
                        } else {
                            ans[it][jt] = '.';
                        }
                    } else { // 当前掩码下该位置不是雷（O）
                        // 逻辑：若结果未标记为X/初始态 → 标记为O；否则标记为.（状态冲突，无法确定）
                        if(ans[it][jt]!='X' && ans[it][jt]!='.'){
                            ans[it][jt] = 'O';
                        } else {
                            ans[it][jt] = '.';
                        }
                    }
                }
                // 情况3：无需判断的空白格 → 直接标记为.
                else {
                    ans[it][jt] = '.';
                }
            }
        }
    }

    // ====================== 步骤5：输出最终结果 ======================
    // 按4x4格式输出结果数组，每行4个字符
    for(ll i=0;i<4;i++){
        for(ll j=0;j<4;j++){
            cout<<ans[i][j];
        }
        cout<<'\n'; // 每行结束换行
    }

    return 0;
}