题目

相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。
万圣节到了 ，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字 表示和它8连通的格子里面雷的数目。
现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图： 由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

  • 大意：固定N*2的扫雷游戏，且第二列没有雷，固定第二列数字，确定第一列雷的排布方案数
  • 思路：容易发现，将第一行第一列的状态（放雷或不放雷）固定之后，根据第一行第二列的数字即可确认下一行第一列是否要放雷，以此类推，下一行是否放雷已经被上一行确定了，即确定了第一行第一列的状态，整个N*2的放雷情况都可以确定。
  • 遇到的问题：雷的排布是否满足扫雷规则，不满足规则的各个情况没有弄清楚。
    一开始，我只想到了等于右侧第二列数值时，下一行不放雷；大于右侧数值则表示不满足扫雷规则；小于右侧数值则下一行放雷。在最后用右侧数值判断这个排布方案是否可行，等于右侧数值即为一种方案。
    之后我尝试了 1 1 2 1 1 这组数据，并逐步输出放雷的情况，发现到有一步，右侧数值比左侧总值大了2（也就是需要放两个雷），因此，得出当小于右侧数值这种情况出现时，有两种情况，右侧数值比左侧总值相差了1，则下一行放雷；右侧数值比左侧总值相差了2，则说明这种放雷的方案出错了。
  • 代码处理：在数组中，我使用1表示在这里放雷，0表示不放雷。然后上文提到的左侧总值，就是第二列的数值所“管理”到的三个数组元素的和。
    #include<bits/stdc++.h>
using namespace std;
int ans;
int a[10010][4];
int main(){
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++){
      cin >> a[i][2];
  }
  for(int i = 0; i <= 1; i++){
      for(int j = 0; j <= n + 10; j++){//进行第二种情况前，需要把“第一列”的值重新置为0
          a[j][1] = 0;
      }
      a[1][1] = i;//两种情况，“第一行第一列”放雷与不放雷
      for(int j = 1; j <= n; j++){
          int sum = 0;
          for(int k = j - 1; k <= j + 1; k++){//计算“左侧总值”
              sum += a[k][1];
          }
          if((j == n) && (sum == a[j][2])){
              ans++;
          }
          if(a[j][2] - sum == 1){
              a[j + 1][1] = 1;
          }else if(a[j][2] - sum > 1) {
              break;
          }else if(sum == a[j][2]) {
              a[j + 1][1] = 0;    
          }else{
              break;
          }
      }
  }
  cout << ans;
  return 0;
}