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

· · 题解

思路：

数据范围这么小，一眼爆搜。注意到最多只有十个位置有问号，因此直接枚举每个问号位置上是地雷还是空地，然后判断情况是否合法即可。注意是多测，记得清空。还有数组要开大点我之前只开到二十错了几遍一直以为是写错了真是蒻完了。

代码如下：

#include<iostream>
#include<string.h>
#define int long long

using namespace std;
const int N=1e2+8;
int T;
int n,m;
int cnt,cnt_;
char a[N][N];
bool f;

struct node
{
    int x;
    int y;
}e[N],op[N];

inline bool check()
{
    for(int i=1;i<=cnt_;i++)
    {
        int x_=op[i].x,y_=op[i].y,sum=0;
        for(int j=x_-1;j<=x_+1;j++)
        for(int k=y_-1;k<=y_+1;k++)
        sum+=(a[j][k]=='*');
        if(sum!=a[x_][y_]-'0')
        return false; 
    }
    return true;
}

inline void dfs(int x)
{
    if(f)return;
    if(x>cnt)
    {
        if(check())
        f=true;
        return;
    }
    a[e[x].x][e[x].y]='*';
    dfs(x+1);
    a[e[x].x][e[x].y]='.';
    dfs(x+1);
}

inline void solve()
{
    cnt=cnt_=f=0;
    memset(a,0,sizeof(a));//多测不清空
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        cin>>a[i][j];
        if(a[i][j]=='?')
        cnt++,e[cnt].x=i,e[cnt].y=j;
        else if('0'<=a[i][j]&&a[i][j]<='8')
        cnt_++,op[cnt_].x=i,op[cnt_].y=j;//记录每个问好和数字的位置
    }
    dfs(1);
    cout<<(!f?"NO\n":"YES\n");
}

signed main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    solve();
    return 0;
}