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

Moanran · 2025-07-17 18:06:31 · 题解

二进制的枚举&剪枝

基本题意简述

• 在输入包含数字，雷，问号三种字符的字符矩阵中，通过确认每个问号是否为雷（可能没有问号），最终判定矩阵是否合规。

基本思路

• 观察题目数据，发现最多只会有十个问号，并且问号最终只会有两种可能性（雷/普通方格）。
• 我们如果用 1 来表示问号变成雷，用 0 来表示问号变成普通方格，已知输入数据后发现一共有 k 个问号，那么就可以把需要枚举的次数，转化为对应 0 ~ 2^k-1 的二进制数。
• 以当前输入数据中有四个问号举例：枚举的情况分别为，0000 , 0001 , 0010 , 0011 , 0100 , 0101 , 0110 , 0111 , 1000 , 1001 , 1010 , 1011 , 1100 , 1101 , 1110 , 1111 。
• 在每枚举一种情况之后，判定当前情况是否合理，如果合理便可以直接剪枝，减少枚举次数。

• 在代码中我们也不需要去特判如果里面没有问号字符的情况，因为它一定会循环至少一次，所以肯定可以去检查一次是否符合要求，而且时间复杂度在这个数据的基础上是应该不会 TLE 的。

  完整代码

• 最后提供一下 AC 代码（包含一定注释），代码略长，但格式还算清晰，存疑的话可以讨论一下~。

#include<bits/stdc++.h>
using namespace std;
char maze[15][15];
int mul=1;
int ditu[15][15];
const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={-1,0,1,-1,1,-1,0,1};
int n,m;
bool first=true;
bool corr=false;
bool bomb[11]={0,0,0,0,0,0,0,0,0,0,0};
struct un
{
    int x;
    int y;
}unk[15];//预处理 
int check()
{
    for(int k=1;k<=n;k++)
    {
        for(int l=1;l<=m;l++)
        {
            if(ditu[k][l]>=0&&ditu[k][l]<=8)
            {
                int cnt=0;
                for(int p=0;p<8;p++)
                {
                    if(maze[k+dx[p]][l+dy[p]]=='*')
                    {
                        cnt++;
                    }
                }
                if(cnt!=ditu[k][l])
                {
                    return 0;
                }
            }
        }
    }
    return 1;
}//检查函数，确认是否每一个数字都满足当前雷的排布 
int top=1;
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        memset(ditu,-1,sizeof(ditu));
        memset(bomb,0,sizeof(bomb));
        corr=false;
        mul=1;
        top=1;//多组数据时记得对每种需要的数据初始化 
        cin>>n>>m;
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)
            {
                cin>>maze[j][k];
                if(maze[j][k]=='?')
                {
                    unk[top].x=j;
                    unk[top].y=k;
                    top++;
                }
                if(maze[j][k]>='0'&&maze[j][k]<='8')
                {
                    ditu[j][k]=maze[j][k]-'0';
                }
            }
        }//输入字符，并分类处理 
        top--;
        for(int i=1;i<=top;i++)
        {
            mul=mul*2;
        }//如果此时没有问号字符，mul=1也会循环一次
        for(int j=0;j<mul;j++)//二进制的想法
        {
            int s=j;
            for(int k=top;k>0;k--)
            {
                bomb[k]=s%2;//反复对2取模，可以获取当前每个问号的状态 
                if(bomb[k])
                {
                    maze[unk[k].x][unk[k].y]='*';
                }
                else
                {
                    maze[unk[k].x][unk[k].y]='.';
                }
                s/=2;
            }
            if(check())
            {
                corr=true;
                cout<<"YES"<<endl;
                break;
            }
        }
        if(!corr)
        {
            cout<<"NO"<<endl;
        }//如果能走到这一步，那这种就一定不满足要求 
    }
    return 0;
}