题解 P2327 [SCOI2005]扫雷

看起来我做的和其他题解不一样

那就发一篇吧

首先本题情况看似无厘头,但是仔细观察,不难发现:

我们可以假设第一种情况,接着可以推出第二种

然后有了两个已知的后,第三个显而易见

如果你要问我怎么推出来的吗,我在里面说的的逻辑判断已经很明白了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;
int boom[10086];
int ans;
int tj[10086];
int looker[10086];
int n;
int pdf() //这段代码是用当前推完的雷局反推右边的数字,如果数字不一样就说明这个雷局不是答案。(因为我们第一颗棋子是假设的)
{
memset(looker,0,sizeof(looker));
for(int i=1;i<=n;i++)
{
if(tj[i]==1)
{
looker[i-1]++;
looker[i]++;
looker[i+1]++;
}
}
for(int i=1;i<=n;i++)
if(looker[i]!=boom[i]) return 0;
return 1;
}
void getnext(int i)
//这是一个判断,这些逻辑的来源是上面一格和二格以及上面一格右边的数字,你可以在草稿纸上手推(反正我就是手推的)
{
if(i==2)
//由于第二个点只能由上面一个点推出因此需要特判
{
if(boom[i-1]==2) tj[i]=1;
if(boom[i-1]==0) tj[i]=0;
if(boom[i-1]==1&&tj[i-1]==1) tj[i]=0;
if(boom[i-1]==1&&tj[i-1]==0) tj[i]=1;
}
else
// 每一行都对应一种情况。括号里是已知情况,括号外为推得当前的雷 tj[i]=1 就说明这个点有雷
{
if(boom[i-1]==0) tj[i]=0;
if(boom[i-1]==3) tj[i]=1;
if(tj[i-2]==0&&tj[i-1]==1&&boom[i-1]==2) tj[i]=1;
if(tj[i-2]==0&&tj[i-1]==1&&boom[i-1]==1) tj[i]=0;
if(tj[i-2]==0&&tj[i-1]==0&&boom[i-1]==1) tj[i]=1;
if(tj[i-2]==1&&tj[i-1]==1&&boom[i-1]==2) tj[i]=0;
if(tj[i-2]==1&&tj[i-1]==0&&boom[i-1]==2) tj[i]=1;
if(tj[i-2]==1&&tj[i-1]==0&&boom[i-1]==1) tj[i]=0;
}
return ;
}
int pd(int f) //函数封装,养成良好习惯
{
memset(tj,0,sizeof(tj));
tj[1]=f;
for(int i=2;i<=n;i++)
getnext(i);
int bj=pdf();
return bj;
}
int main()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&boom[i]);
ans+=pd(0);//两种情况都要枚举并且验证,答案有可能为0
ans+=pd(1);
printf("%d",ans);
return 0;
}
Author: MMMsc0.618
Link: http://yoursite.com/2019/10/20/题解-P2327-SCOI2005-扫雷/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付宝

Comment