[BZOJ 1088][SCOI2005]掃雷Mine

Description

相信大家都玩過掃雷的游戲。那是在一個n*m的矩陣裡面有一些雷，要你根據一些信息找出雷來。萬聖節到了，“余”人國流行起了一種簡單的掃雷游戲，這個游戲規則和掃雷一樣，如果某個格子沒有雷，那麼它裡面的數字表示和它8連通的格子裡面雷的數目。現在棋盤是n×2的，第一列裡面某些格子是雷，而第二列沒有雷，如下圖： 由於第一列的雷可能有多種方案滿足第二列的數的限制，你的任務即根據第二列的信息確定第一列雷有多少種擺放方案。

Input

第一行為N，第二行有N個數，依次為第二列的格子中的數。（1<= N <= 10000）

Output

一個數，即第一列中雷的擺放方案數。

Sample Input

Sample Output

HINT

Source

可以說是水題吧。。。只需要確定第一行有無地雷即可，第0行可視作無地雷，這樣就能確定第二行。然後第一、二行都確定下來了，就能確定第三行。以此類推，所有地雷分布情況都能通過枚舉第一行的情況確定下來，只需要在推完後對第n+1行做判斷，如果第n+1行有地雷，則推錯了，推理不成立。記錄下推理正確的方案個數

#include 
#include 
#define MAXN 10010
int 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;
}