https://ac.nowcoder.com/acm/problem/20241
题意：
一个只有两列的扫雷，其中第二列没有雷，并且给出了第二列的数字，该数字表示以其为中心连通的八个格子共含雷的数量，问第一列雷有多少摆放方案？

分析：
很有趣的一道模拟题，按照题意自己手动模拟答案发现其实第一列雷的方案数基本都被第二列给限制死了，能让你二选一的其实很少了（为什么扫雷高级还是过不了QAQ）

a[i]：第二列第i个数的值
f[i]：第一列的i个数是否有雷，1代表有，0代表无
f[i-1]+f[i]+f[i+1]=a[i]-->f[i+1]=a[i]-f[i-1]-f[i]（扫雷规则）

先整体来看，显然对于每个a[i]的值均不能超过3，因为棋盘只有一列有雷，即以某点为中心最多只有3颗雷，特别的，第一个数和最后一个数不能超过2，因为有一个被挡住了。按顺序先从第一个值进行考虑，共有3种可能，0，1，2。
如果第一个数为0：第一列第1，2个位置可推出没有雷，通过f[i+1]=a[i]-f[i-1]-f[i]递推下去每个位置是否有雷为固定答案。
如果第一个数为2：第一列的第1，2个位置可推出均为雷，同上式可推出每个位置是否有雷为固定答案。
如果第一个数为1：那么则可能有2个答案，第一列的第1个位置有雷或者是第二个位置有雷，当其中一个位置有雷，即可推出另一个了，已知两个位置，用上面的递推式即可确定之后是否有雷了。

最后把其他格子的数枚举判断是否合法即可ac了。

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[10004];
int f[10004],n,i,j,ans,flag;
int hi(){
    for(int j=2;j<n;j++){//从2开始判断
        int t=a[j]-f[j-1]-f[j];//判断第i+1处是否有雷
        if(t<0 || t>1)  return 0;//不符合标准
        else    f[j+1]=t;
    }
    if(f[n]+f[n-1]!=a[n]){//特批一下最后两个
        return 0;
    }
    return 1;
}
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]>3) flag=1;
    }
    if(a[1]>2 || a[n]>2 || flag){
        printf("0\n");
        return 0;
    }
    if(a[1]==2){
        f[1]=1;
        f[2]=1;
        ans+=hi();
    }
    else if(a[1]==0){
        f[1]=0;
        ans+=hi();
    }
    else if(a[1]==1){
        f[1]=1;//地雷放第一个
        ans+=hi();
        memset(f,0,sizeof(f));
        f[2]=1;//地雷放第二个
        ans+=hi();
    }
    printf("%d",ans);
}

解法二：

可以用dfs暴瘦一下
每个点只能是有或者没有地雷，按照这两个状态进行搜索即可。
每次枚举完记得判断一下是否为可行解,进行剪枝。
注意一下第一个点要分类讨论放不放地雷。

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 10004
int n;
int a[maxn],b[maxn];
int ans;
void dfs(int x)
{
    int sum=0;
    if(b[x-1]) sum++;
    if(b[x]) sum++;
    if(sum==a[x]-1)//下一个点必须是地雷
    {
        if(x+1 > n) return ; 
        b[x+1]=1;//有地雷
        dfs(x+1);
        b[x+1]=0;
    }
    if(sum!=a[x]) return;
    if(x==n)
    {
        ans++;
        return;
    }
    dfs(x+1);//没有地雷。
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    b[1]=1;dfs(1);
    memset(b,0,sizeof(b));dfs(1);
    printf("%d\n",ans);
    return 0;
}