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

HNO_3 · 2025-11-05 20:49:07 · 题解

B4167 [GXPC-S 2024] 扫雷 题解

• 对于本题，我们可以采用类似状压（状态压缩）的方式进行解决，用 01 串表示，1 表示雷（同时 ? 的数量小于等于 10 也是突破口），然后依照题意遍历判断即可 QwQ。 ::::success[code]

  #include<bits/stdc++.h>
  #define il inline
  using namespace std;
  typedef long long ll;
  typedef pair<int,int> pii;
  il ll read(){
  ll x=0;bool f=0;char ch=getchar();
  while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();}
  while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return f?-x:x;
  }
  il void write(ll x){
  if(x<0) x=-x,putchar('-');
  if(x>9) write(x/10);
  putchar(x%10|48);
  }
  char a[10][10];
  pii b[11];
  int n,m,k;
  bool f=0;
  il bool check1(int x,int y){
  return x<0||x>=n||y<0||y>=m;
  }
  bool vis[11][11];
  il void check(int x){
  for(int j=k-1;~j;--j){
      int t=j+1;
      if((x>>j)&1) vis[b[t].first][b[t].second]=1;
      else vis[b[t].first][b[t].second]=0;
  }
  for(int i=0;i<n;++i)
      for(int j=0;j<m;++j)
          if(isdigit(a[i][j])){
              int p=a[i][j]^48,cnt=0;
              for(int x=-1;x<=1;++x)
                  for(int y=-1;y<=1;++y){
                      if(!x&&!y) continue;
                      int nx=i+x,ny=j+y;
                      if(check1(nx,ny)) continue;
                      if(a[nx][ny]=='*') ++cnt;
                      else if(a[nx][ny]=='?'&&vis[nx][ny]) ++cnt;
                  }
              if(cnt!=p) {f=1;return ;}
          }
  }
  il void solve(){
  n=read(),m=read(),k=0;
  for(int i=0;i<n;++i){
      scanf("%s",a[i]);
      for(int j=0;j<m;++j){
          if(a[i][j]=='?')
              b[++k]=make_pair(i,j);
      }
  }
  for(int i=0;i<=(1<<k)-1;++i){
      f=0;
      check(i);
      if(!f) {puts("YES");return ;}
  }
  puts("NO");
  }
  int main()
  {
  int T=read();
  while(T--) solve();
  return 0;
  }

  :::: （￣︶￣）↗　如有问题还请指出。