问题描述
有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。
输入格式
第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。
输出格式
最多能拿金币数量。
样例输入
3
1 3 3
2 2 2
3 1 2
样例输出
11
数据规模和约定
n<=1000
就是我想着判断他的大小,然后行和列一旦有一方到顶直接另一方走到头请问对吗
#include <stdio.h>
int x[1000][1000];
int main()
{
int i,j,n,st_h=0,st_l=0,sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++){
scanf("%d",&x[i][j]);
}
}
sum+=x[0][0];
while(1){
if(st_h+1==n){
for(st_l+=1;st_l<n;st_l++){
sum+=x[st_h][st_l];
}
break;
}
if(st_l+1==n){
for(st_h+=1;st_h<n;st_h++){
sum+=x[st_h][st_l];
}
break;
}
i=x[st_h+1][st_l];
j=x[st_h][st_l+1];
if(i>j){
sum+=i;
st_h+=1;
}else{
sum+=j;
st_l+=1;
}
}
printf("%d",sum);
return 0;
}
每走一个格子都判断右和下哪个金币多
这个代码试试能不能过
#include <stdio.h>
int t[1000][1000];
int main()
{
int i,j,n,h=0,l=0,sum=0;
scanf("%d",&n);
for(i=0; i<n; i++)
for(j=0; j<n; j++)
scanf("%d",&t[i][j]);
sum+=t[0][0];
while(h<n-1||l<n-1)
{
if(h==n-1)
{
sum+=t[h][++l];
continue;
}
if(l==n-1)
{
sum+=t[++h][l];
continue;
}
if(t[h+1][l]>t[h][l+1])
sum+=t[++h][l];
else
sum+=t[h][++l];
}
printf("%d",sum);
return 0;
}