P2327 [SCOI2005] 扫雷（枚举详解）c++

题目链接：P2327 [SCOI2005] 扫雷 - 洛谷

1.题目分析

假设第一个，第一层有雷，第二层肯定没雷，因为有雷的话，两个雷加起来就超过第一层的信息1了，第三层肯定有雷，因为第二层的2可得知在离它最近的三层里面有两个雷，第三层的3决定了离它最近的3层格子要有3个雷，此时第二层没雷的话，即使第四层有雷也凑不出3个雷，所以当前是错误的判断；假设第二个，第一层没雷，第二层一定有雷，第三层格必定有雷，根据第三层的3判断出来，第四个必定有雷，根据第四层的2判断第五层肯定没雷，因为第四层的2决定了离它最近的3层里面有两个雷，前面已经存在了两个雷，下面就不能再出现了，接着第五层的2决定了第六层有雷，第六层对应的2确定了最后一层肯定有雷，所以这是一个正确的方案

第一层摆放确定后，后面的格子都可以推导出来，第一层格子要么有雷要么没雷，所以我们只要枚举第一层格子有没有雷就可以了，所以最多只有两种方案

2.算法原理

解法：枚举第一列的第一个格子，有没有放雷

我们用b数组存有数数列，a数组推导有没有摆放雷，0无1有，下标从1开始，第一种情况，a[1]=0，第一层没雷，b[1]决定了a[0]a[1]a[2]里面雷的总个数，a[1]=0可以顺势推出，a[2]=b[1]-a[0]-a[1]=1，同理a[3]=b[2]-a[1]-a[2]=1，依此往下计算可得公式，a[i]=b[i-1] - a[i-2] - a[i-1]，上面的格子减去上层已知的对应的格子雷数，当我们推导出a[i]<0，说明欠雷了，或者是a[i]>1，说明超雷了，不符合要求，返回false即可

第一层是1，第二层是3，假设第一层没雷，推导出第二层是1，假设数组长度为n，枚举到n，在第二层停的话，看似是合法的，因为b[n](第二层的3)的值没有判断，3决定要再放两个雷，但在但三层放两颗地雷是不合法的，在这道题里面是找不到摆放方式的，刚刚只算到n就结束了，并没有算到n+1，细节就是，一会计算a数组时，要算到n+1，在判断n+1是否为0，n+1不等于0的话，说明是缺地雷的，b[n]是不合法的，要处理这种情况

如果下标从0开始计数，a[0]值已经确定，但推导a[1]时，a[1]=b[0]-a[-1]-a[0]，就会发生越界访问的情况，程序报错，下标从1开始计数，全局数组a[0],b[0]的值就为0，是不影响计数结果的        

 代码：

#include <iostream>
using namespace std;

const int N = 1e4 + 10;
int n;
int a[N], b[N];

//不放地雷
int check1()
{
	a[1] = 0;
	for (int i = 2; i <= n + 1; ++i)
	{
		a[i] = b[i - 1] - a[i - 2] - a[i - 1];
		if (a[i] < 0 || a[i] > 1) return 0;
	}
	if (a[n + 1] == 0) return 1;
	else return 0;
}

//放地雷
int check2()
{
	a[1] = 1;
	for (int i = 2; i <= n + 1; ++i)
	{
		a[i] = b[i - 1] - a[i - 2] - a[i - 1];
		if (a[i] < 0 || a[i] > 1) return 0;
	}
	if (a[n + 1] == 0) return 1;
	else return 0;

}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> b[i];

	//要么b[1]这个格子放或是不放
	int ret = 0;
	ret += check1(); //判断a[1]不放地雷
	ret += check2(); //判断a[1]放地雷

	cout << ret << endl;

	return 0;
}