[SCOI2005]扫雷MINE

传送门

题意：

有一个n行两列的矩阵，第一列放雷，第二列代表其周围八个方向的总雷数，现在给你第二列的数，求第一列雷有多少种摆法？

思路：

对于第一个格子，只有有雷和没有雷的情况，而当第一个格子确定了，根据第二列的第一个和第二个数和第三个数就能确定第二个格子有没有雷，所以这个题只需要讨论第一个格子有没有雷，然后挨个判断合理不变合理即可

因为tr[i] = mine[i - 1] + mine[i] + mine[i + 1]

用i - 1代替i，并移向可得到：

mine[i] = tr[i - 1] - mine[i - 1] - mine[i - 2]

可以用来判断i大于等于2的时候

只需要判断mine[i]每个数是不是为0或1，如果不是，说明该种策略不合理

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 10000 + 5
typedef  long long ll ;
//不开longlong见祖宗！

int tr[MAX], mine[MAX], n;

int f(int x){//x是mine的第一个数，传0或1
    mine[1] = x;
    for(int i = 2; i <= n; ++i){
        mine[i] = tr[i - 1] - mine[i - 1] - mine[i - 2];
        if(mine[i] == 1 || mine[i] == 0)
            continue;
        else return 0;//不合理
    }
    if(mine[n] + mine[n - 1] != tr[n])//对于最后一个数要特判
        return 0;
    return 1;
}

int main()
{
    cin>>n;
    for(int i = 1; i <= n; ++i)cin>>tr[i];
    int sum = 0;
    sum += f(1);
    memset(mine, 0, sizeof(mine));//进行第二次判断，清0
    sum += f(0);
    cout<<sum<<endl;
    return 0;
}