首页 > 代码库 > BZOJ1088: [SCOI2005]扫雷Mine
BZOJ1088: [SCOI2005]扫雷Mine
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
这很明显是一道水题。看上去像是DP，但其实如果定了前2位，则可以完全推得n个位置。然后最后判断最后2个位置是否符合要求，hzwer说这是模拟题。
然后，当n==1时无需特判，但是存在aa[1]==0的情况（第一次WA了没有考虑到）。
1 /************************************************************** 2 Problem: 1088 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:8 ms 7 Memory:900 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 template<class T>inline void readin(T &res) {12 static char ch;T flag=1;13 while((ch=getchar())<‘0‘||ch>‘9‘)if(ch==‘-‘)flag=-1;14 res=ch-48;while((ch=getchar())>=‘0‘&&ch<=‘9‘)res=(res<<1)+(res<<3)+ch-48;res*=flag;15 }16 const int N = 10010;17 int n, aa[N], bb[N], ans, ok;18 bool check() {19 for( int i = 2; i <= n-1; i++ ) {20 bb[i+1]=aa[i]-bb[i]-bb[i-1];21 if(bb[i+1]<0||bb[i+1]>1) return 0;22 }23 return bb[n-1]+bb[n]==aa[n];24 }25 int main() {26 readin(n);for( int i = 1; i <= n; i++ ) readin(aa[i]);27 if(n==1||aa[1]==0) ans+=check();28 else if(aa[1]==1) {29 bb[1]=0;bb[2]=1;ans+=check();30 bb[1]=1;bb[2]=0;ans+=check();31 } else if(aa[1]==2) {32 bb[1]=1;bb[2]=1;ans+=check();33 }34 printf("%d\n",ans);35 return 0;36 }37
BZOJ1088: [SCOI2005]扫雷Mine
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。