第六节蓝桥杯 方格填数

转载请注明出处：http://www.cnblogs.com/zhishoumuguinian/p/8392793.html
标题：方格填数在2行5列的格子中填入1到10的数字。要求：相邻的格子中的数，右边的大于左边的，下边的大于上边的。如【图1.png】所示的2种，就是合格的填法。请你计算一共有多少种可能的方案。请提交该整数，不要填写任何多余的内容（例如：说明性文字）。

           

思路：我先做的第七届的题，这个题的思路和第七届的《第七届蓝桥杯 方格填数》，《第七届蓝桥杯 寒假作业》思路是一样的。那也粘上代码。

代码运行结果：42

 

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <math.h>
 4 
 5 using namespace std;
 6 
 7 int ans=0;
 8 int a[2][5];
 9 int flag[15]={0};
10 bool Check(int x, int y)
11 {
12     if(x==0&&y==0)
13     return true;
14     if(x==0)
15     {
16         if(a[x][y-1]<a[x][y]) return true;
17     }
18     else
19     {
20         if(y==0)
21         {
22             if(a[x-1][y]<a[x][y]) return true;
23         }
24         else
25         {
26             if((a[x][y-1]<a[x][y])&&(a[x-1][y]<a[x][y])) return true;
27         }
28         
29     }
30     return false;
31 }
32 void dfs(int x, int y)
33 {
34     if(x==2)
35     {
36         ans++;
37         return;
38     }
39     for(int i=1; i<=10; i++)
40     {
41         if(flag[i]==0)
42         {
43 
44           a[x][y]=i;
45           flag[i]=1;
46           if(Check(x,y))
47           {
48             if(y<4) dfs(x,y+1);
49             else dfs(x+1,0);
50           }
51           flag[i]=0;
52         }
53     }
54 }
55 
56 int main()
57 {
58     dfs(0,0);
59     cout<<ans;
60     return 0;
61 }