OJ题号：
BZOJ1088、洛谷2327
思路：
经过观察可以发现，如果一个格子是否有雷可以通过其右上角的数字、上方两个格子是否有雷确定。因此我们可以假定第一个格子是否有雷的情况，递推求解。
如果递推过程中发现一个格子中的地雷数大于一个或者少于零个，则说明这种情况不成立。
1 #include<cstdio> 2 #include<cctype> 3 inline int getint() { 4 char ch; 5 while(!isdigit(ch=getchar())); 6 int x=ch^‘0‘; 7 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘); 8 return x; 9 } 10 const int N=10002; 11 int a[N],b[N]; 12 int n; 13 inline bool check() { 14 for(int i=2;i<=n+1;i++) { 15 b[i]=a[i-1]-b[i-2]-b[i-1]; 16 if(b[i]!=1&&b[i]!=0) return false; 17 } 18 return b[n+1]==0; 19 } 20 int main() { 21 n=getint(); 22 a[0]=a[n+1]=1; 23 for(int i=1;i<=n;i++) a[i]=getint(); 24 int ans=0; 25 b[1]=0; 26 if(check()) ans++; 27 b[1]=1; 28 if(check()) ans++; 29 printf("%d\n",ans); 30 return 0; 31 }
原文：http://www.cnblogs.com/skylee03/p/7381029.html