题意

给定2行的矩阵 , 第一行为扫雷的格子 , 即描述下方最近3格的雷的个数 ; 第二行为雷或空

求满足第一列限制的第二列的雷摆放方法数

思路

本来以为是dp , 没想到是思维题..

考虑已经知道第i个格子有没有雷和对应的数字

数字有三种可能 , 0 , 1, 2

如果是0 , 那么下一个格子肯定没有雷 ;

如果是1 , 那么根据当前i格子有无雷可以知道下一个格子 ;

如果是2,3 , 那么肯定有

感悟是读完题一定要耍几个例子试试 , 不要空想

代码

#include

using namespace std;

const int N = 1e4+10;

int a[N];

int main() {

int n;

cin >> n;

for (int i = 1; i <= n; i++) cin >> a[i];

int ans = 0;

for (int init = 0; init <= 1; init++) {

int valid = 1;

int pre = 0, f = init;

if ((f==0 && a[1] >=2) || (f==1 && a[1] == 0)) continue;

for (int i = 2; i <= n; i++) {

int tmp = f;

f = a[i-1] - f- pre;

pre = tmp;

if (f < 0 || f > 1) {

valid = 0;

break;

}

}

if (f + pre != a[n])

valid = 0;

if (valid) ans++;

}

cout << ans;

return 0;

}

//1 1 2 1 1

//1 0 1 1 0

//0 1 0 1 0