竞赛讨论区 > 【每日一题】6月19日题目精讲—扫雷
头像
王清楚
编辑于 2020-06-19 11:24
+ 关注

【每日一题】6月19日题目精讲—扫雷

题号 NC20241
名称 [SCOI2005]扫雷MINE
来源 [SCOI2005]
戳我进入往期每日一题汇总贴~
往期每日一题二期题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

因为第二列的情况已经确定了,那么我们只需要枚举第一列的第1个雷放还是不放,然后根据第二列第一个数就能确定第二列第二个位置放还是不放,依此类推,直到确定最后一行的情况,或者发现矛盾为止(方案数最多等于2,只要第一个格子确定了放不放雷,之后的就确定了)。

还有同学使用dp做法的,当前行第二列的数值显然与左边三个格子有关——i-1,i,i+1,又因为我们的状态是从上一行转移来,所以记录两个格子的情况就可以了,f[i][j][k]表示当前在第i行,当前行是不是雷,下一行是不是雷的方案数。
a[i]==0,当前行、这一行和上一行都不能是雷:
f[i][0][0]+=f[i-1][0][0];
a[i]==1,当前行、这一行和上一行只有一个是雷:
f[i][0][0]+=f[i-1][1][0];
f[i][1][0]+=f[i-1][0][1];
f[i][0][1]+=f[i-1][0][0];
a[i]==2,当前行、这一行和上一行有两个是雷:
f[i][1][1]+=f[i-1][0][1];
f[i][0][1]+=f[i-1][1][0];
f[i][1][0]+=f[i-1][1][1];
a[i]==3,当前行、这一行和上一行都是雷:
f[i][1][1]+=f[i-1][1][1];
最终的答案应该是f[n][0][0]+f[n][1][0].

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目6月26日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

全部评论

(10) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐