自动搬运

查看原文

来自洛谷，原作者为

	Moanran 执大师之剑，谱英杰之诗

搬运于2025-08-24 21:17:31，当前版本为作者最后更新于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;
}