BZOJ 1088: [SCOI2005]扫雷Mine
正文索引 [隐藏]
Description
相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图： 由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。
Input
第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）
Output
一个数，即第一列中雷的摆放方案数。
Sample Input
2
1 1
1 1
Sample Output
2
题解
每一格都可以通过，前两个的情况推出来，所以，我们只需要枚举可能有变的前两格。（最近软件写多了。。命名有一点。。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<cstdio> using namespace std; const int Maxn=11000; int layout[Maxn]; int require[Maxn]; int n; int Ans=0; inline int check(){ for (int i=2;i<=n;i++){ if (layout[i]+layout[i-1]>require[i]) return 0; layout[i+1]=require[i]-(layout[i]+layout[i-1]); if (layout[i+1]>1) return 0; } if (layout[n+1]>0) return 0; return 1; } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%d",&require[i]); for (layout[1]=0;layout[1]<=1;layout[1]++){ for (layout[2]=0;layout[2]<=1;layout[2]++){ if (layout[1]+layout[2]==require[1]) Ans+=check(); } } printf("%d\n",Ans); return 0; } |
原文链接：BZOJ 1088: [SCOI2005]扫雷Mine
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!