走的时候只能一格一格的走，走的方向只能往下或往右，并且不能走出边界。从入口进来，每个格子代表通过这个格子的时间。Helihui规定最左上角是通道入口， 最右下角是通道出口，现在要求你判断从入口到出口的所有路径中总时间最小的那条路径。并输出通过该条路径的总时间，上面的红色箭头是表示这样走可以得到最小的总时间。
输入数据有多组。
每组输入n,m整数，n表示通道格子的行数，m表示通道格子的列数，0<n，m<100，接下来输入n行m列的矩阵，矩阵的数据的范围0到32765。
走的时候从通道入口进入从出口出去，并且通道入口一直在最左上角，通道出口一直在最右下角。
输出从入口到出口所有路径中最短时间
这个怎么做啊？？？

对不起以我的智商还不能解答此题，呵呵。

这个好像是穷举法。。。还没学过。。。求指教！


上句扯淡。。。Dijkstra算法。。。

[ 本帖最后由 qldxsun 于 2011-6-9 23:16 编辑 ]

动态规划  我先去吃饭 吃晚饭给你写代码

顶老杨，

动态规划。

#include <stdio.h>
int path[100][100] = {0};
int Min(int a,int b)
{
    return a<b ? a:b;
}
int main()
{
    int m,n;
    int i,j;
    while(EOF != scanf("%d %d",&m,&n))
    {
        for(i = 0;i<m;i++)
            for(j = 0;j<n;j++)
            {
                scanf("%d",&path[i][j]);
                if(i == 0 && j == 0)
                    continue;
                if(i == 0)
                {
                    path[i][j] += path[i][j-1];
                }
                else if(j == 0)
                {
                    path[i][j] += path[i-1][j];
                }
                else
                {
                    path[i][j] += Min(path[i-1][j],path[i][j-1]);
                }
            }
        printf("%d\n",path[m-1][n-1]);
    }
    return 0;
}

台州OJ测试AC了

老杨 能不能解释下动态规划啊 求指教

怎么说呢 动态规划有很多种 上面的就是个类树型的动态规划 但是不是树形的

因为矩阵边缘的点只有一条路可走  还有很多 比如线性的 背包问题...

如果你有兴趣学的话+我QQ 553069938 我晚上吧资料给你