http://www.lydsy.com/JudgeOnline/problem.php?id=1088
2*N的扫雷棋盘，第二列的值a[i]记录第 i 个格子和它8连通的格子里面雷的数目。
第一列的雷可能有多种方案满足第二列的数的限制，根据第二列的信息确定第一列雷有多少种摆放方案。
设第一列的值为b[i]，不难得出以下递推关系
b[0] + b[1] = a[0]
b[0] + b[1] + b[2] = a[1]
...
b[i] = a[i-1] - a[i-2] + b[i-3]
或 b[i] = a[i-1] - b[i-1] - b[i-2]
由此发现，b[0]、b[1]确定了，后续的b[i]也由递推式唯一的确定了。而又有b[0]+b[1] = a[0]的限制条件，故可根据a[0]的值枚举b[0], b[1]的组合，然后顺次求出b[i], 判断每个b[i]值是否合法，一旦发现不合法，则此种枚举情况不成立。
程序流程图如下（这里的“合法”判断与具体位置有关，如a[0], a[n-1] <3, a[n-1] == b[n-1] + b[n-2]）：
代码如下（为了直观表达流程图，用了goto语句）：
#include <cstdio>
using namespace std; int n;
int a[];
int b[]; int main()
{
scanf("%d", &n);
for(int i=; i<n; i++){
scanf("%d", &a[i]);
}
int cnt = ; for(int i=; i<n; i++){ //非法
if(a[i]< || a[i]>){
goto L;
}
}
if(a[n-]== || a[] == ){ //非法
goto L;
} if(a[] == ) b[] = b[] = ;
else if(a[] == ) b[] = b[] = ; if(a[] == ) goto B; b[] = a[] - a[]; //0或2的情况
if(b[] < || b[] > ){
goto L;
}
for(int i=; i<n; i++){
b[i] = a[i-] - a[i-] + b[i-];
if(b[i] < || b[i] > ){
goto L;
}
}
if(b[n-] + b[n-] != a[n-]) //检查最后一个a
goto L;
printf("1\n");
return ; B: b[] = ; b[] = ; //01或10的情况
b[] = a[] - a[];
if(b[] < || b[] > ){
goto L1;
}
for(int i=; i<n; i++){
b[i] = a[i-] - a[i-] + b[i-];
if(b[i] < || b[i] > ){
goto L1;
}
}
if(b[n-] + b[n-] != a[n-])
goto L1;
cnt++; L1: b[] = ; b[] = ; //试探另一种
b[] = a[] - a[];
if(b[] < || b[] > ){
goto L;
}
for(int i=; i<n; i++){
b[i] = a[i-] - a[i-] + b[i-];
if(b[i] < || b[i] > ){
goto L;
}
}
if(b[n-] + b[n-] != a[n-])
goto L;
cnt++; L: printf("%d\n", cnt);
return ; }
BZOJ 1088