# 扫雷(mine clearance)-其他

## 扫雷(mine clearance)

### 输入数据 1

``````2
1 1``````

### 输出数据 1

``2``

### 数据范围与提示

1<=N<=1000

那么 观察可以发现 我们已知第二列的雷  就可以用第二列的数字来判断 某个位置是否有雷 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 10010using 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;}``
————————

### Title Description

I believe everyone has played the game of minesweeping. Halloween is coming, and a simple mine sweeping game is popular in the “Yu” people’s country. The rules of the game are the same as mine sweeping. If there is no mine in a grid. Then the numbers in it represent the number of mines in the lattice that is not connected with it······

Now the chessboard is n * 2. Since the mines in the first column may have multiple schemes to meet the limit of the number of mines in the second column, your task is to determine how many placement schemes there are for the mines in the first column according to the information in the second column.

< strong > input format < / strong >

The first row is n, and the second row has n numbers, which are the numbers in the second column grid in turn.

### Output format

A number, that is, the number of mine placement schemes in the first column.

### Input data 1

``````2
1 1``````

### Output data 1

``2``

### Data range and tips

1<= N<= one thousand

< strong > problem solution: < / strong >

In fact, this problem reduces the difficulty and is set to n × 2 grid. If this question is set to n × N Lattice, it must not be solved by brute force method.

If the brute force method is used to solve, each lattice has thunder or no thunder, a total of n * n lattices, and the algorithm complexity is O (2 ^ n * n), which is absolutely undesirable.

But this problem is n * 2 lattice. All interested UU might as well try the brute force method, but I still don’t recommend Austria. Here are my recommended ideas (simulated DP):

It can be found from the observation that if we know the mines in the second column, we can use the numbers in the second column to judge whether there are mines in a certain position. If a is determined, we can deduce B. if B is determined, we can deduce C according to a, B, a and B. that is, after the current two positions are determined, the positions of the whole column of mines are determined – verifiable

“`

``//// Created by 23011 on 14/1/2022.//#include<iostream>#define MAXN 10010using 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;}``