首页 > 其他分享 >[SCOI2005]扫雷

[SCOI2005]扫雷

时间:2022-11-08 14:01:54浏览次数:52  
标签:int 位置 dfs -- 扫雷 && 情况 SCOI2005

题目描述

相信大家都玩过扫雷的游戏。那是在一个\(n\times m\)的矩阵里面有一些雷,要你根据一些信息找出雷来。万圣节到了,“余”人国流行起了一种简单的扫雷游戏,这个游戏规则和扫雷一样,如果某个格子没有雷,那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是\(n\times 2\)的,第一列里面某些格子是雷,而第二列没有雷,如下图:

由于第一列的雷可能有多种方案满足第二列的数的限制,你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

输入格式

第一行为N,第二行有N个数,依次为第二列的格子中的数。(1<= N <= 10000)

输出格式

一个数,即第一列中雷的摆放方案数。

样例 #1

样例输入 #1

2 1 1

样例输出 #1

2

不成功的尝试

据同学们说,这是一道非常水的题
但是对我来说,还是有一点点难的。读题,我第一反应是一道特判题,我自己也不知道为什么 ,然后我就在草稿纸上开始了……
于是,我就有了第一个错误的程序

#include<bits/stdc++.h>
using namespace std;
const int inf=0x7fffffff;
int n,a[10004];
bool flag=0;
int b[10004];
int main(){
//	freopen("sweeper.in","r",stdin);
//	freopen("sweeper.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]!=1){
			flag=1;
		}
	}
	if(flag==0){
		if(n%3==2){
			cout<<2;
			return 0;
		}
	}
//	cout<<1;
	for(int i=1;i<=n;i++){
		if(a[i]==3){
			b[i]=b[i+1]=b[i-1]=1;
			a[i]=0;
			a[i+1]-=2;
			a[i-1]-=2;
			if(i+2<=n){
				a[i+2]-=1;
			}
			if(i-2>=1){
				a[i-2]-=1;
			}
		}
	}//处理3 
	for(int i=1;i<=n;i++){
		if(a[i]==0){
			if(b[i+1]!=1){
				b[i+1]=inf;
			}
			if(b[i]!=1){
				b[i]=inf;
			}
			if(b[i-1]!=1){
				b[i-1]=inf;
			}
		}
	}//处理0
	for(int i=1;i<=n;i++){
		if(a[i]<0){
			cout<<0;
			return 0;
		}
	}
	for(int i=1;i<=n-2;i++){
		if(a[i]==1&&a[i+1]==2&&a[i+3]==1){
			cout<<0;
			return 0;
		}
		if(a[i]==2&&a[i+1]==2&&a[i+2]==2){
			cout<<0;
			return 0;
		}
	}
	cout<<1;
	return 0;
}

你没有看错,全是特判然后就wa了40分(好像确实数据很水

思路

经过在草稿纸上的模拟后,我发现全部由1组成的序列且个数为mod3余2的情况下,总会有两种情况。

接下来就是不存在的情况。我们知道对于3来说,它上下三个位置一定有雷,而对于0,上下三个位置一定没有0。于是我们特判这两种情况,如果不成立,则输出0。

剩下的情况自然就是1了。

代码(有点丑

#include<bits/stdc++.h>
using namespace std;
int n,a[10004],ans=0,b[10004],f=0;
void dfs(int x){
	if(f!=-1) f=0;
	for(int i=1;i<=n;i++){
		if(a[i]!=0){
			f=1;
			break;
		}
	}
	if(f==0){
		return ;
	}
	if(x==n+1||f==-1){
		f=-1;
		return ;
	}
	if(x+1<=n&&x-1>=1){
		if(a[x+1]>=1&&a[x]>=1&&a[x-1]>=1){
			a[x+1]--;
			a[x]--;
			a[x-1]--;
		}
		dfs(x+1);
	}
	if(x==1){
		if(a[x+1]>=1&&a[x]>=1){
			a[x+1]--;
			a[x]--;
		}
		dfs(x+1);
	}
	if(x==n){
		if(a[x-1]>=1&&a[x]>=1){
			a[x-1]--;
			a[x]--;
		}
		dfs(x+1);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	if(n==1&&a[1]==1){
		cout<<1;
		return 0;
	}
	dfs(1);
	if(f==0){
		ans++;
	}
	for(int i=1;i<=n;i++){
		a[i]=b[i];
	}
	f=0;
	dfs(2);
	if(f==0){
		ans++;
	}
	if(ans==2&&b[1]==0){
		cout<<1;
		return 0;
	}
	cout<<ans;
	return 0;
}

两个dfs就搞定

思路

经过前面的瞎搞,我们知道了最多有两种情况

证明:
每一个数字代表了上下三块的地雷情况
所以情况种类只可能是mod3
即0,1,2

那么,已经知道了只可能这三种情况,那么我们就枚举从第一号位置有雷和第一号位置没有雷这两种情况,那么最简单的办法就是分别从一号位置开始和第二号位置开始两次dfs
dfs的思路就很简单了,如果上下三个都比一大那么这个位置就是可以放置地雷的,我们一直枚举到n+1的位置如果到这时都依旧满足,则此情况成立,分别跑两次,如果两次都成立,则答案为2,同理可得1种情况和不成立

意外

写完了dfs以后,90分!!!???为什么?
经过自己造了n组数据以后,终于发现了问题所在:当序列的第一位为0时,一号位置和二号位置都不能放置地雷,这样一来,一号位置就和二号位置等效了
那么我们只需要特判以下,如果第一位为0,那么,如果是两种情况,那么就要在这个基础上减去一个,但是如果不成立的话就不用特判了

	if(ans==2&&b[1]==0){
		cout<<1;
		return 0;
	}

终于做完了,这道题debug好久

标签:int,位置,dfs,--,扫雷,&&,情况,SCOI2005
From: https://www.cnblogs.com/GXYZY/p/16869457.html

相关文章

  • 体验【应用交付扫雷大作战】,得程序员专属帆布袋
    【体验技能Get】✅一个平台,搞定应用全生命周期管理✅白屏化部署,轻松上手K8s✅发布可观测可干预,发布信心十足【体验奖品Get,100%拿】云效新老用户均可参与,1000份云效定......
  • 扫雷
    这周经过我艰辛的奋斗,完成了个扫雷的小代码,创建了两个棋盘,一个是放置雷(0/1),另一个棋盘存储信息,存储我输入坐标进行游戏扫雷存放的信息,同时每扫一个坐标会将坐标周围的8个位置......
  • PyGame做了一个扫雷
     1#这是一个示例Python脚本。23#按⌃R执行或将其替换为您的代码。4#按双击⇧在所有地方搜索类、文件、工具窗口、操作和设置。5importsy......
  • 【SCOI2005】骑士精神(IDA_,A_)
    我们先考虑最纯粹的暴力,也就是暴力枚举每次空格调到哪里,并继续递归求解。然后发现\(O(8^{15}\times5\times5)\)的复杂度限制了我们的想象。同学写了一发好像10分然后既......
  • P1896 [SCOI2005] 互不侵犯
    #include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<cmath>usingnamespacestd;#definelllonglongintn,k;llf[10][(......
  • BZOJ 1084([SCOI2005]最大子矩阵-长矩阵Dp)
    1084:[SCOI2005]最大子矩阵TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 586  Solved: 275[​​Submit​​][​​Status​​][​​Discuss​​]De......
  • ABAP游戏:扫雷
    效果:代码*&---------------------------------------------------------------------**&ReportZLM_GAME2*&-----------------------------------------------------------......
  • 扫雷游戏---手把手教程(含源码)【C语言】
    ......
  • [SCOI2005] 骑士精神 题解
    题目描述解法采用IDA*算法。不移动骑士而移动空格。每次限制深度,然后对每个遍历到的点进行一次估价,估价函数的值即为当前状态和终点的差异数。如果估计的加上已经确......
  • docker搭建扫雷小游戏
    下载HTML文件包链接:https://pan.baidu.com/s/1AFfkQMKBjAspgGNldRmHXQ提取码:9adg复制这段内容后打开百度网盘手机App,操作更方便哦下载httpd镜像[root@docker~]#......