思路

N * 2 的矩阵

那就尝试枚举第一列的每个格子，有雷或者没有雷 ， 时间复杂度O(2 ^ N) ， 这里N = 10000 明显会超时

这个题我看了下其他人的题解， 一种是用暴力搜索， 然后大量的减枝 , 另一种是用递推关系式, 有点像动态规划

1. 暴力搜索减枝版

用 a[N]存第一列的数字 , b[N] 数组第二列是否有雷

每次搜索 bfs(x) : b[x-1] , b[x] , b[x+1] 和 a[x] 的关系
根据不同的情况枚举 bfs(x + 1)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = INT_MAX;
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int>> small_heap;
#define int long long

int32_t main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1, 0), b(n + 1, 0);

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int ans = 0;
    function<void(int)> dfs = [&](int x)
    {
        int s = b[x - 1] + b[x];
        if (s + 1 == a[x]) // 下一个一定是雷
        {
            if (x == n) return; // 失败的情况
            b[x + 1] = 1;
            dfs(x + 1);   // 暴搜选择
            b[x + 1] = 0; // 暴搜不选
        }
        if (s != a[x])  return;
        if (x == n)
        {
            ans++;
            return;
        }
        dfs(x + 1);
    };
    b[1] = 1;
    dfs(1);
    b.assign(b.size(), 0);
    dfs(1);
    cout << ans;
    return 0;
}

2.动态规划

这里直接截图佬的图了, 不是因为我懒 alt

然后依据扫雷游戏的规则，我们有公式：
map[i] = mine[i-1] + mine[i] + mine[i+1]
移项一下，用i-1替换i，可以得到：
mine[i] = map[i - 1] - mine[i - 1] - mine[i - 2]
利用这个规则，我们可以推断mine[2]以及后面的值。因为这是一个一次公式，而且mine的前两个元素的值已知，所以对于每一确定的map，mine的摆放最多只有两种可能

推断出所有的mine以后，再判断mine里的值是否合法即可（只能是0或1） 佬的代码

#include <iostream>

using namespace std;

int isPossible(int *map, int *mine, int N) {
//  依据公式:
//      map[i] = mine[i-1] + mine[i] + mine[i+1]
//  逐个计算第一列格子中是否存在地雷，并判断是否合法
    for (int i = 2; i < N; ++i) {
        mine[i] = map[i - 1] - mine[i - 1] - mine[i - 2];
        if (mine[i] < 0 || mine[i] > 1)return 0;
    }
//  最后两行单独判断
    if (mine[N - 1] + mine[N - 2] != map[N - 1])return 0;
    return 1;
}

int main() {
    int temp;   //工具人变量
    int N;  //第二列格子的个数
    cin >> N;
    int map[N]; //第二列格子里的数
    int mine[N];    //第一列格子的雷的个数(只能是0或1)
    for (int i = 0; i < N; ++i) {
        cin >> map[i];
    }
//  如果只有一个格子，直接输出1
    if (N == 1) {
        cout << 1 << endl;
        return 0;
    }
    int res = 0;    //可能的摆放方案数

//  依据第二列第一个格子里的数计算方案数
    switch (map[0]) {
//      第一个格子为0，即第一列前两个格子都 没有 地雷
        case 0:
            mine[0] = 0;
            mine[1] = 0;
            cout << isPossible(map, mine, N);
            break;

//      第一个格子为2，即第一列前两个格子都 有 地雷
        case 2:
            mine[0] = 1;
            mine[1] = 1;
            cout << isPossible(map, mine, N);
            break;

//      第一个格子为1，即第一列 前两个格子中 仅有一个 地雷
        case 1:
//          把两种情况都计算一下可能性，加起来再输出
            mine[0] = 0;
            mine[1] = 1;
            res += isPossible(map, mine, N);
            mine[0] = 1;
            mine[1] = 0;
            res += isPossible(map, mine, N);
            cout << res;
            break;

//      第一个格子不是0，1，2，即非法地图，输出0
        default:
            cout << 0 << endl;
    }
}