PIPI玩扫雷

题目描述

现在PIPI在玩一个简单版的扫雷游戏，地图为一个N行2列的矩阵，左边列的格子都未打开，且格子只有两种情况：有地雷，无地雷(即空格子)。右边列的格子已经全部打开，且都为数字（只包含0,1,2,3），数字表示和它8连通的格子里面雷的数目，如下图例子所示。

请你帮PIPI计算出左边列的雷可能有多种方案满足第二列的数的限制。

输入

第一行为一个整数N，N<=100000.
接下来N个数字，表示右边列格子中的数字。

输出

输出左边列合法的方案数。

样例输入

2
1 1

样例输出

2

思路：这题首先要知道当左边这列的第一个值确定时，整个左边这列的值就确定了，比如第一个值为0时，第二个值等于前一列右边的值减去左边一行和前一行的值，mp[i][0]=mp[i-1][1]-mp[i-1][0]-mp[i-2][0]，其次就是左边的第一行不能为3，最后一行的值要验证，因为左边这列的最后一行的值是通过前n-1行确定的，所以最后要验证一下mp[n][0]+mp[n-1][0]!=mp[n][1]

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int mp[N][2],flag;
int main(){
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&mp[i][1]);
    }
    if(mp[1][1]==3){
        printf("0\n");
        return 0;
    }
    for(int j=0;j<2;j++){
        flag=0;
        mp[1][0]=j;
        for(int i=2;i<=n;i++){
            mp[i][0]=mp[i-1][1]-mp[i-1][0]-mp[i-2][0];
            //printf("%d%d%d",mp[i-1][1],mp[i-1][0],mp[i-2][0]);
            if(mp[i][0]==0||mp[i][0]==1)
                continue;
            else{
                flag=1;
                break;
            }
        }
        if(mp[n][0]+mp[n-1][0]!=mp[n][1]) flag=1;
        if(flag==0) ans++;
    }
    printf("%d\n",ans);
}