[Luogu P2327] [BZOJ 1088] [SCOI2005]扫雷

洛谷传送门

BZOJ传送门

题目描述

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

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

输入输出格式

输入格式：

第一行为N$N$，第二行有N$N$个数，依次为第二列的格子中的数。（1≤N≤10000$1\le N\le 10000$）

输出格式：

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

输入输出样例

输入样例#1：

2
1  1

输出样例#1：

2

解题分析

这道题当然可以dp$dp$， 但是记录3$3$个格子的状态转移太麻烦了。

事实上我们只要确定第一列第一个格子填不填雷就可以通过第二列第一个格子推出第一列第二个格子填不填雷了， 以此类推。 所以我们只要钦定第一个格子的填法即可。

代码如下：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define R register
#define IN inline
#define gc getchar()
#define W while
#define MX 10050
template <class T>
IN void in(T &x)
{
    x = 0; R char c = gc;
    for (; !isdigit(c); c = gc);
    for (;  isdigit(c); c = gc)
    x = (x << 1) + (x << 3) + c - 48;
}
int fir[MX], sec[MX], len, ans = 2;//答案最多为2
void check()
{
    int bd = len + 1;
    for (R int i = 2; i <= bd; ++i)
    {
        fir[i] = sec[i - 1] - fir[i - 1] - fir[i - 2];
        if(fir[i] != 1 && fir[i] != 0) return --ans, void();
        if(i == bd && fir[i]) return --ans, void();
    }
}
int main(void)
{
    in(len);
    for (R int i = 1; i <= len; ++i) in(sec[i]);
    fir[1] = 1; check();
    fir[1] = 0; check();
    printf("%d", ans);
}