P2327 [SCOI2005] 扫雷题目分析本题是一个有趣的递推问题。棋盘是n × 2 n \times 2n×2的第一列可能埋有地雷第二列没有地雷。关键点由于棋盘只有2列第二列每个格子只能与第一列的3个方向左上、左、左下的格子相邻因此数字表示的是第一列相邻格子中雷的数量。解题思路核心观察一旦确定了第一列第一个格子是否有雷整个第一列的雷的分布就唯一确定了。相邻关系与推导设a [ i ] a[i]a[i]表示第二列第i ii行的数字l [ i ] l[i]l[i]表示第一列第i ii行是否有雷1有雷0无雷第二列第i ii个格子与第一列的相邻关系第1行边界a [ 1 ] l [ 1 ] l [ 2 ] a[1] l[1] l[2]a[1]l[1]l[2]只能看到第一列第1行和第2行第i ii行1 i n 1 i n1ina [ i ] l [ i − 1 ] l [ i ] l [ i 1 ] a[i] l[i-1] l[i] l[i1]a[i]l[i−1]l[i]l[i1]能看到第一列第i − 1 i-1i−1、i ii、i 1 i1i1行第n nn行边界a [ n ] l [ n − 1 ] l [ n ] a[n] l[n-1] l[n]a[n]l[n−1]l[n]只能看到第一列第n − 1 n-1n−1行和第n nn行递推公式由a [ 1 ] l [ 1 ] l [ 2 ] a[1] l[1] l[2]a[1]l[1]l[2]得l [ 2 ] a [ 1 ] − l [ 1 ] l[2] a[1] - l[1]l[2]a[1]−l[1]由a [ i ] l [ i − 1 ] l [ i ] l [ i 1 ] a[i] l[i-1] l[i] l[i1]a[i]l[i−1]l[i]l[i1]得l [ i 1 ] a [ i ] − l [ i ] − l [ i − 1 ] l[i1] a[i] - l[i] - l[i-1]l[i1]a[i]−l[i]−l[i−1]算法流程枚举第一种可能第一个格子没有雷l [ 1 ] 0 l[1]0l[1]0枚举第二种可能第一个格子有雷l [ 1 ] 1 l[1]1l[1]1对每种可能用递推公式计算后续所有格子检查过程中每个l [ i ] l[i]l[i]是否合法只能是0或1最后验证边界条件a [ n ] l [ n ] l [ n − 1 ] a[n] l[n] l[n-1]a[n]l[n]l[n−1]完整代码#includebits/stdc.husingnamespacestd;intn;vectorinta,l;// a为第二列数字l为第一列雷的状态boolcheck(intfirst_cell){l[1]first_cell;// 设定第1格状态if(n1)returna[1]l[1];// 特判只有1行的情况l[2]a[1]-l[1];// 由a[1] l[1] l[2]推导if(l[2]0||l[2]1)returnfalse;for(inti2;in;i){l[i1]a[i]-l[i]-l[i-1];// 由a[i] l[i-1] l[i] l[i1]推导if(l[i1]0||l[i1]1)returnfalse;}returna[n]l[n]l[n-1];// 验证边界a[n] l[n-1] l[n]}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cinn;a.resize(n1);l.resize(n1);for(inti1;in;i)cina[i];intans0;if(check(0))ans;// 第1格没雷if(check(1))ans;// 第1格有雷coutans;}