题目描述
相信大家都玩过扫雷的游戏。那是在一个\(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