三角形
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;
}