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

· · 题解

好久没写题解了……

题意解释

题目传送门。

思路分析

一眼数据范围，直接想到大爆搜，具体思路如下：

  1. 寻找所有 ? 的格子，记下位置与总数量。
  2. 搜索遍历，把所有这样的格子搜一遍，有雷无雷都试一遍。
  3. 每试完一遍就判断一下合不合法，合法直接标记。
  4. 按标记结果输出。

时间复杂度：\mathcal{O}(2^{cnt}nm)。

代码实现

::::warning[不要抄袭]

#include<bits/stdc++.h>
using namespace std;

struct node{
    int x,y;
}pos[105];
int T,n,m,cnt;
bool flag;
char mp[15][15];
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

bool check()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j]>='0'&&mp[i][j]<='9')
            {
                int sum=mp[i][j]-'0';
                for(int k=0;k<8;k++)
                {
                    int xx=dx[k]+i;
                    int yy=dy[k]+j;
                    if(xx<1||xx>n||yy<1||yy>m) continue;
                    if(mp[xx][yy]=='*') sum--;
                }
                if(sum!=0) return false;
            }
    return true;
}
void dfs(int i)
{
    if(i==cnt+1)
    {
        if(check()) flag=1;
        return;
    }
    mp[pos[i].x][pos[i].y]='.';
    dfs(i+1);
    mp[pos[i].x][pos[i].y]='*';
    dfs(i+1);
    return;
}
int main()
{
    cin>>T;
    while(T--)
    {
        cnt=flag=0;
        memset(pos,0,sizeof pos);   
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {               
                cin>>mp[i][j];
                if(mp[i][j]=='?') 
                {
                    cnt++;
                    pos[cnt].x=i,pos[cnt].y=j;
                }
            }
        dfs(1);
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
 }

:::::

结束！