bzoj 1088: [SCOI2005]扫雷Mine

2023-08-12 11:00:22

1088: [SCOI2005]扫雷Mine

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2525 Solved: 1495
[Submit][Status][Discuss]

Description

相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图：由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

Input

第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）

Output

一个数，即第一列中雷的摆放方案数。

Sample Input

2
1 1

Sample Output

确定了第一行的情况之后其他的都可以推出来。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

int a[], f[], ans, n;

int cal() {

    for(int i = ; i<=n; i++) {

        f[i+] = a[i]-f[i-]-f[i];

        if(f[i+]<)

            return ;

    }

    if(a[n]!=f[n]+f[n-])

        return ;

    return ;

}

int main()

{

    cin>>n;

    for(int i = ; i<=n; i++) {

        scanf("%d", &a[i]);

    }

    if(a[] == ) {

        ans += cal();

    } else if(a[] == ) {

        f[] = ;

        ans += cal();

        mem(f);

        f[] = ;

        ans += cal();

    } else {

        f[] = f[] = ;

        ans += cal();

    }

    cout<<ans<<endl;

    return ;

}

码农公寓