扫雷MINE

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

输入描述:

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

输出描述:

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

输入：

2
1 1

输出：

2

思路： 算法核心：枚举
简单的熄灯问题，枚举优化，注意到只要确定了第一个空的状态，第二空的状态也是定的，以此类推，只要看最后一个空是否合理就行（代码有详注

#include <iostream> 
#include <cstring>
#include <cstdio>
using namespace std;
int arr[10005];//存输入的数据 
int res[10005];//存方案 
int n,cnt=0;//计数多少种方案 
bool check()//通过arr最后一个数，检查扫雷的第一列是否合理 
{
	if(arr[n]-res[n]-res[n-1]==0)	return true;
	else return false ;
}
void dfs(int pos)//用了搜索的板子写枚举 
{
	int i,j,k;
	if(pos==n+1)//当最后一个空填完后，检查 
	{
	if(check()) cnt++;//如果合理，计数+1 
	return ;
	}
	res[pos]=arr[pos-1]-res[pos-1]-res[pos-2];//每个位置是否有雷，等于右上角的数字减去上面两个空的雷数 
	if(res[pos]<0)	return; //如果出现负数，直接排除 
	dfs(pos+1);//搜索下一位 
}
int main()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++)	cin>>arr[i];
	res[1]=0;dfs(2);//若第一个位置无雷 
	memset(res,0,sizeof(res));//清空记录 
	res[1]=1;dfs(2);//若第二个位置有雷 
	cout<<cnt<<endl;
	
}