题解：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;
}