FAFU OJ 三角形

xiaoxiao2021-02-27  150

三角形 Time Limit:1000MSMemory Limit:65536KBTotal Submissions:99Accepted:62 Share Description:       设有如下图所示数字三角形,编写程序,计算从顶至底的所有路径所经过的数字总和。         ①每个数字点,只可沿左斜线向下或右斜线向下,如:第一行的7只能走到第二行3或8,第三行的1只能走到第四行的7或4。第四行的7只能走到第五行的5或2。         ②1≤三角形行数≤20         ③三角形中的数字为0到10的整数         7         3 8         8 1 0         2 7 4 4         4 5 2 6 5         Input: 输入的第一行是三角形的总行数,接下去是每行的数字,数字间用空格分隔。 Output: 输出包括一行,输出从顶至底,所经过的路径的数字和。 Sample Input: 3 7 3 8 8 1 0 Sample Output: 60 Source: #include<stdio.h> int n,ans; int a[25][25]; void dfs(int x,int y,int s) { if(x==n) { ans+=s; return; } dfs( x+1,y,s+a[x+1][y] ); dfs(x+1,y+1,s+a[x+1][y+1]); } int main() { int i,j; while(scanf("%d",&n)==1) { for(i=1;i<=n;i++) for(j=1;j<=i;j++) scanf("%d",&a[i][j]); dfs(1,1,a[1][1]); printf("%d",ans); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-16176.html

最新回复(0)