https://i.cnblogs.com/posts/edit;postId=15800443

题目描述

相信大家都玩过扫雷的游戏。万圣节到了，「余」人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷。那么它里面的数字表示和它不连通的格子里面的雷的数目······

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

 

输入格式

第一行为N,第二行有N个数，依次为第二列格子中的数。

输出格式

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

样例

输入数据 1

2
1 1

输出数据 1

2

数据范围与提示

1<=N<=1000

题解：

其实这道题降低了难度，设置的是ｎ×２的格子。假如此题设置的是ｎ×ｎ的格子，那一定不能用蛮力法来求解。

假如用蛮力法求解，每个格子有雷 or 无雷，一共n*n个格子，算法复杂度为O(2^n*n),绝对不可取。

但是这道题是n*2的格子，所有感兴趣的uu不妨试试蛮力法，但是我还是不推荐奥。以下是我推荐的思路（模拟dp）：

 那么 观察可以发现 我们已知第二列的雷
 就可以用第二列的数字来判断 某个位置是否有雷
 A a
 B b
 C c
 D d
 E e
 如果确定了A 那么可以推出B
如果确定了B 根据a，b，A，B 可以推出C
 也就是当前两个位置确定后那么整列雷的位置都确定了——可证

```

//
// Created by 23011 on 14/1/2022.
//


#include<iostream>
#define MAXN 10010
using namespace std;

int a[MAXN],n;

inline int check(int now) {//now代表当前位置是否有雷
    int last=0;//last上一个位置是否有雷
        for(int i=1;i<n;i++) {
             int next=a[i]-last-now;//下一个位置是否有雷
             if(next<0||next>1) return 0;//当前情况合不合法
             last=now;
             now=next;
        }
        if(last+now!=a[n]) return 0;//最后一个格子合不合法
        else return 1;
}

 int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    printf("%d\n",check(0)+check(1));
    return 0;
}