nyoj-----幸运三角形
幸运三角形
- 描述
-
话说有这么一个图形,只有两种符号组成(‘+’或者‘-’),图形的最上层有n个符号,往下个数依次减一,形成倒置的金字塔形状,除第一层外(第一层为所有可能情况),每层形状都由上层决定,相邻的符号相同,则下层的符号为‘+’,反之,为‘-’;如下图所示(n = 3 时的两种情况):
如果图中的两种符号个数相同,那这个三角形就是幸运三角形,如上图中的图(2).
代码:
1 #include<stdio.h> 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<pos;i++) //下一城 13 { 14 if(map[pos][i]==map[pos][i+1]) map[pos-1][i]=1; //tong wei 1 15 else map[pos-1][i]=0; 16 if(map[pos][i]) ans++; 17 if(4*ans>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 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。