黑马程序员技术交流社区

标题: 求数组最小和路径 [打印本页]

---

作者: 李东城    时间: 2013-2-6 18:10
标题: 求数组最小和路径
求数组最小和路径。
给定数组：从左上角走到右下角，每次可以沿着8个方向自由走一步，经过的路径要求和，问怎样走能得到最小和路径。输出这条路径每个格的坐标。
0    3    2    6    2    1
2    1    7    2    5    3
1    6    3    3    2    4
1    1    5    7    3    1
1    9    9    8    2    5
1    9    2    9    2    0

好像是蓝桥杯竞赛的一道题。
感觉应该是用回溯法，百度了好半天，找到个相关帖子，他说用迪杰斯特拉算法，可是看了半天没看明白，他说沿8个方向走，不是只需要计算超右走和超下走就可以了么？
求解释一下，求指导，求教育...

---

作者: 郭孟涛    时间: 2013-2-6 20:00
如果选择了周围比较小的，造成路径返回。反而走了弯路。也会使总和变大。分析了一下还是很复杂的。{:soso_e100:}

最近发现不少类似这样的数学问题，我觉得除了在考察对java语言运用的熟练程度以外，更多的是数学的解答方法。
至于用java、c++、还是asp.net等等都不是重点。只是格式有些不同。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2