专栏文章

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

___Kyw666__
B4167题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimyxxdz
此快照首次捕获于
2025/12/01 17:50
3 个月前
此快照最后确认于
2025/12/01 17:50
3 个月前
查看原文
好久没写题解了……

题意解释

题目传送门。

思路分析

一眼数据范围，直接想到大爆搜，具体思路如下：
  1. 寻找所有 ? 的格子，记下位置与总数量。
  2. 搜索遍历，把所有这样的格子搜一遍，有雷无雷都试一遍。
  3. 每试完一遍就判断一下合不合法，合法直接标记。
  4. 按标记结果输出。
时间复杂度：O(2cntnm)\mathcal{O}(2^{cnt}nm)。

代码实现

不要抄袭CPP
#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;
 }
结束！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...