首页 > 代码库 > [BZOJ 1088][SCOI2005]扫雷Mine

[BZOJ 1088][SCOI2005]扫雷Mine

2024-07-07 16:46:45   219人阅读

Description

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

Input

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

Output

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

Sample Input

2
1 1


Sample Output

2

HINT

Source

可以说是水题吧。。。只需要确定第一行有无地雷即可，第0行可视作无地雷，这样就能确定第二行。然后第一、二行都确定下来了，就能确定第三行。以此类推，所有地雷分布情况都能通过枚举第一行的情况确定下来，只需要在推完后对第n+1行做判断，如果第n+1行有地雷，则推错了，推理不成立。记录下推理正确的方案个数

#include <stdio.h>#include <string.h>#define MAXN 10010int l1[MAXN],l2[MAXN],n; //l1[i]=1表示第1列第i行有雷,l2[i]=第2列第i行的数int check() //判断是否满足要求，是返回1，不是返回0{	int i,j;	for(i=2;i<=n;i++)		l1[i+1]=l2[i]-l1[i]-l1[i-1]; //推导第3行及以后的地雷分布情况	if(l1[n+1]) return 0; //如果第一列第n+1行有雷，则表明推理不成立，返回0	return 1;}int main(){	int i,j,cnt=0;	scanf("%d",&n);	for(i=1;i<=n;i++)		scanf("%d",&l2[i]);	for(i=0;i<=l2[1];i++)//只需要枚举第一列第一行是否有雷，接着就能推出第二行到第n行的雷的分布情况	{		memset(l1,0,sizeof(l1));		l1[1]=i;		l1[2]=l2[1]-i;		if(check()) cnt++;	}	printf("%d\n",cnt);	return 0;}


 

 

 

 


联系
我们