【每日一题】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之前写的题解有获得牛币资格~

.牛币兑换中心