幸运三角形

时间限制：

1000

 ms  |  内存限制：

65535

 KB

难度：

3

 

描述

        话说有这么一个图形，只有两种符号组成（‘+’或者‘-’），图形的最上层有n个符号，往下个数依次减一，形成倒置的金字塔形状，除第一层外（第一层为所有可能情况），每层形状都由上层决定，相邻的符号相同，则下层的符号为‘+’，反之，为‘-’;如下图所示（n = 3 时的两种情况)：

                                           

如果图中的两种符号个数相同，那这个三角形就是幸运三角形，如上图中的图（2）.

 

输入

有多组测试数据（少于20组）。

每行含一个整数n（0<n<20)。

输出

输出相应的幸运三角形个数。

样例输入

34

样例输出

46

来源

上传者

dfs搜索。。。。

代码：

1 #include
      
        2 int str[20]={
    0}; 3 bool map[20][20]; 4 void dfs(int x,int pos) 5 { 6     int i; 7     if(x==pos) 8     { 9         int ans=0;10         do{11            if(map[pos][pos]) ans++;12           for(i=1;i
       
        x*(x+1)) return ;18           }19         }while(--pos);20         if(4*ans==x*(x+1)) str[x]++;21         return ;22     }23     map[x][pos+1]=0;   //采用横向搜索24     dfs(x,pos+1);25     map[x][pos+1]=1;26     dfs(x,pos+1);27 }28 int main()29 {30     int n,i;31     for(i=1;i<19;i++)32     {33         if(i%4==3||i%4==0)dfs(i,0);34     }35     str[19]=32757;36     while(scanf("%d",&n)!=EOF)37     {38         printf("%d\n",str[n]);39     }40     return 0;41 }