扫雷(mine clearance)

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

题目描述

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

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

输入格式

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

输出格式

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

样例

输入数据 1

2
1 1

输出数据 1

2

数据范围与提示

1<=N<=1000

题解:

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

假如用蛮力法求解,每个格子有雷 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 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;}
————————

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

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.

Sample

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;}