首页 > 代码库 > 【暴力】【推导】bzoj1088 [SCOI2005]扫雷Mine
【暴力】【推导】bzoj1088 [SCOI2005]扫雷Mine
考虑右侧的一个格子是否放雷，只可能对其左侧的三个格子造成影响。
也就是说，若左侧一个格子旁的两个格子已经放了雷，对第三个格子也就唯一确定了。
因此只枚举前两个格子是否放雷，剩下的暴力判断是否合法即可。
但是再想想，左侧第一个格子只受右侧前两个格子的影响。所以只枚举右侧第一个格子是否放雷，剩下的判断是否合法即可。
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int n,a[10001],t[10001],ans; 5 bool b[10001]; 6 int main() 7 { 8 scanf("%d",&n); 9 for(int i=1;i<=n;i++) scanf("%d",&a[i]);10 memcpy(t,a,sizeof(a));11 b[1]=1; a[1]--; a[2]--;12 for(int i=2;i<=n;i++)13 if(a[i-1])14 {15 b[i]=1; a[i-1]--; a[i]--; a[i+1]--;16 if(a[i-1]!=0) goto FAIL;17 }18 if(a[n]!=0||a[n-1]!=0) goto FAIL;19 ans++;20 FAIL: memset(b,0,sizeof(b));21 memcpy(a,t,sizeof(a));22 for(int i=2;i<=n;i++)23 if(a[i-1])24 {25 b[i]=1; a[i-1]--; a[i]--; a[i+1]--;26 if(a[i-1]!=0) goto FAIL2;27 }28 if(a[n]!=0||a[n-1]!=0) goto FAIL2;29 ans++;30 FAIL2: printf("%d\n",ans);31 return 0;32 }
【暴力】【推导】bzoj1088 [SCOI2005]扫雷Mine
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。