题目
Description
给定M*N的矩阵，其中的每个元素都是-10到10之间的整数。你的任务是从左上角（1，1）走到右下角（M，N），每一步只能向右或向下，并且不能走出矩阵的范围。你所经...
题目
Description
给定M*N的矩阵，其中的每个元素都是-10到10之间的整数。你的任务是从左上角（1，1）走到右下角（M，N），每一步只能向右或向下，并且不能走出矩阵的范围。你所经过的方格里面的数字都必须被选取，请找出一条最合适的道路，使得在路上被选取的数字之和是尽可能小的正整数。
Input
第一行两个整数M，N，（2<=M,N<=10），分别表示矩阵的行和列的数目。
接下来的M行，每行包括N个整数，就是矩阵中的每一行的N个元素。
Output
仅一行一个整数，表示所选道路上数字之和所能达到的最小的正整数。如果不能达到任何正整数就输出-1。
思路
将到i,j取得的值都保存，取一个最小值。（自己的想法）
发现内存挺大的，速度也不够快。。。
代码
#include<cstdio>
int m,n,a,f[12][12][2010]={0};
int main(){
scanf(\"%d%d\",&m,&n);
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j){
scanf(\"%d\",&a);
if(i==1) f[i][j][0]=1,f[i][j][1]=f[i][j-1][1]+a;
else if(j==1) f[i][j][0]=1,f[i][j][1]=f[i-1][j][1]+a;//特殊处理
else{
for(int k=1;k<=f[i-1][j][0];k++){ //从上来的可能
f[i][j][0]++;
f[i][j][f[i][j][0]]=a+f[i-1][j][k];
}
for(int k=1;k<=f[i][j-1][0];k++){ //从左来的可能。
f[i][j][0]++;
f[i][j][f[i][j][0]]=a+f[i][j-1][k];
}
}
}
int ans=10000001;
for(int i=1;i<=f[m][n][0];++i) //找最小值
if(ans>f[m][n][i]&&f[m][n][i]>0) ans=f[m][n][i];
if(ans==10000001) ans=-1;
printf(\"%d\",ans);
}
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
