[洛谷 2327][SCOI2005]扫雷

题目链接

https://www.luogu.org/problem/P2327

题解

一道很不错的思维题。

事实上,确定了第一个格子的状态,就可以推出其他格子的状态。

所以枚举第一个格子是否有雷即可。(答案也只有三种情况:0,1,2)

#include <stdio.h>
#include <string.h>
int a[10005],b[10005];
int main()
{
 int n,ans=2;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  scanf("%d",&a[i]);
 b[1]=1;
 for(int i=2;i<=n+1;i++)
 {
  b[i]=a[i-1]-b[i-1]-b[i-2];
  if(b[i]!=0&&b[i]!=1)
  {
   ans--;
   break;
  }
  if(b[n+1]!=0)ans--;
 }
 memset(b,0,sizeof(b));
 for(int i=2;i<=n+1;i++)
 {
  b[i]=a[i-1]-b[i-1]-b[i-2];
  if(b[i]!=0&&b[i]!=1)
  {
   ans--;
   break;
  }
  if(b[n+1]!=0)ans--;
 }
 printf("%d\n",ans);
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注