P2327 [SCOI2005]扫雷

倚窗倾听风吹雨

https://www.luogu.org/problemnew/show/P2327

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

由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

输入文件：  第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）

输出文件：一个数，即第一列中雷的摆放方案数。输入输出举例：

输入：                             输出：

2                               2

1 1

倚窗倾听风吹雨

1. #include<iostream>
   
2. #include<cstdio>
   
3. using namespace std;
   
4. int a[10010],ans,n,num;
   
5. bool visit[10010];
   
6. bool judge(int x)
   
7. {
   
8.         if(visit[x-1]+visit[x]+visit[x+1]==a[x])return true;
   
9.         else return false;
   
10. }
    
11. void dfs(int x)
    
12. {
    
13.         if(x>2)
    
14.         if(!judge(x-2))return;
    
15.         if(x>n)
    
16.         {
    
17.                 if(judge(x-1))
    
18.                 {
    
19.                         /*for(int i=1;i<=n;i++)
    
20.                     cout<<visit[i]<<" ";
    
21.                     cout<<endl;*/
    
22.                     ans++;
    
23.                 }
    
24.                
    
25.                 return;
    
26.         }
    
27.         for(int i=0;i<=1;i++)
    
28.         {
    
29.                 visit[x]=i;
    
30.                 dfs(x+1);
    
31.         }
    
32. }
    
33. int main()
    
34. {
    
35. //        freopen("mine.in","r",stdin);
    
36. //        freopen("mine.out","w",stdout);
    
37.         cin>>n;
    
38.         for(int i=1;i<=n;i++)
    
39.         cin>>a[i];
    
40.         dfs(1);
    
41.         cout<<ans;
    
42. //        fclose(stdin);
    
43. //        fclose(stdout);
    
44.         return 0;
    
45. }
    

复制代码