[SCOI2005]扫雷Mine

1088: [SCOI2005]扫雷Mine

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2028  Solved: 1187
[Submit][Status][Discuss]

Description

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

Input

第一行为N,第二行有N个数,依次为第二列的格子中的数。(1<= N <= 10000)

Output

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

Sample Input 1

2
1 1

Sample Output 1

2

Sample Input 2(这个是我自己加的,可能有人会错)

3
5 8 5

Sample Output 2

4

HINT

 

Source

                        [Submit][Status][Discuss]
 

分析

  由于这是一个N*2的棋盘,所以如果第二行都没有地雷,则第一行只要确定前两个格子的数,后面的自然可以递推出来。可以这么理解:假设我们要确定第一行第 i (i>=3) 个格子的地雷数,则要满足:first[i-2]+first[i-1]+first[i]==second[i-1]。当i==2时,first[i]=second[i-1]-first[i-1](first[2]=second[1]-first[1]),所以只要从0开始枚举first[1]的可能值就可以了。

 #include<bits/stdc++.h>
using namespace std;
const int maxn=;
int N,ans=;
int sec[maxn];
int fir[maxn];
bool jud();
int main(){
scanf("%d",&N);
for(int i=;i<=N;i++)
scanf("%d",&sec[i]);
for(int i=;i<=sec[];i++){
memset(fir,,sizeof(fir));
fir[]=i;
fir[]=sec[]-i;
if(jud()==true){
ans++;
}
}
cout<<ans;
return ;
}
bool jud(){
for(int i=;i<=N+;i++){
fir[i]=sec[i-]-fir[i-]-fir[i-];
}
if(fir[N+]) return false;
return true;
}

  特别小心:

  第27行的fir[N+1]可绝对不能改成fir[N+1]>0,因为可能存在负值,比如我上面给出的样例2。5 8 5是第二行,而且第一行可以推出1 4 3 -2的情况。我就因为这个WA了好多次。但是吧,写 fir[N+1]!=0 是 beyond all doubt √ 的,全怪我手贱。。。

上一篇:webpack --- 详解


下一篇:Web前端,HTML5开发,前端资源,前端网址,前端博客,前端框架整理 - 转改