NC20241 SCOI2005 扫雷MINE

文中数组下标均从0开始

地图上有两列，mine对应第一列，表示格子里的地雷数（0或1），map对应第二列，表示附近的地雷数

根据map[0]的值，我们可以推断mine[0]和mine[1]地雷的存在情况，如：

然后依据扫雷游戏的规则，我们有公式：
    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;
    }
}