求数组最小和路径。
给定数组：从左上角走到右下角，每次可以沿着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个方向走，不是只需要计算超右走和超下走就可以了么？
求解释一下，求指导，求教育...

[ 本帖最后由 a287154777 于 2013-2-4 13:40 编辑 ]

这是一个算法问题
8个方向都可以走的，例如
0 9 9
9 1 9
1 9 9
1 1 1

如果碰到这样的情况就要往左下走了，所以往上 往左也不是不可能

挺有意思的有木有人贴下源码看看学习下啊？

public class Graph {
    private Vertex[] vertexs;
    private int[][] adjMat;
    private int length = 0;
    static final int INFINITY = ~(1 << 31); // 整数的最大值，表示没有路径

    Graph(int size) { // 初始化
        vertexs = new Vertex[size];
        adjMat = new int[size][size];
        for (int i = 0; i < size; i++)
            // 将邻接矩阵初始化为全部不通
            for (int j = 0; j < size; j++)
                adjMat[i][j] = INFINITY;
    }

    public static void main(String[] args) {
        Graph g = new Graph(36);
        int x[][]={
                {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}};
        // 添加节点
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                StringBuilder sb=new StringBuilder();
                sb.append("[").append(i).append(",").append(j).append("](").append(x[i][j]).append(")");
                g.add(sb.toString());
            }
        }
        // 添加有向有权边
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                int vx=i-1,vy=j-1;
                while(vy<=j+1 && vy<6){
                    if(vx<0 || vy<0 || vx>=6 || (vx==i && vy==j)){
                       

                    }else{
                        g.connect(i*6+j, vx*6+vy, x[vx][vy]);
                    }
                    vx++;
                    if(vx>i+1 || vx>=6){
                        vx=i-1;
                        vy++;
                    }
                }
            }
        }
        Path p = g.path(0); // 获得最小路径
        p.print(); // 打印
    }
   

    void add(Object value) { // 添加顶点
        assert length <= vertexs.length;
        vertexs[length++] = new Vertex(value);
    }

    void connect(int from, int to, int length) {
        adjMat[from][to] = length; // 设置指定节点之间的有向路径
    }

    /**
     * 在邻接矩阵中，查找指定顶点的未访问过邻居顶点 如果从从起点到终点的边存在，且没有标志为访问，则返回终点下标。
     *

     * @param offset
     *            指定开始查找的列
     * @param index
     *            指定查找的行
     */
    int findNeighbor(int index, int offset) {
        for (int i = offset; i < length; i++) {
            if (adjMat[index][i] != INFINITY && !vertexs[i].isVisited())
                return i;
        }
        return -1;
    }

    Vertex get(int index) {
        return vertexs[index];
    }

    Path path(int index) { // 最小路径算法
        assert vertexs[index] != null;
        Path result = new Path(length, index, this); // 初始化Path
        vertexs[index].visit(); // 将其实节点标志为访问过
        for (int n = 1; n < length; n++) { // 一共经过n此迭代就可得到最终结果
            int i = -1;
            while ((i = findNeighbor(index, i + 1)) != -1)
                // 寻找当前节点的所有为访问邻居
                result.adjust(index, i, adjMat[index][i]); // 根据新路线调整最小路径
            index = result.getMin(); // 将当前节点更新为路径表中为访问的最近的那个节点
            vertexs[index].visit(); // 将当前节点标志为访问过;
        }
        clean();
        return result;
    }

    boolean isVisited(int index) {
        return vertexs[index].isVisited();
    }

    void clean() {
        for (Vertex v : vertexs)
            if (v != null)
                v.clean();
    }

}
class ParentLength { // 记载上一个节点与当前最小路径
    private int parent; // 上一个节点
    private int length; // 最小路径长度

    ParentLength(int parent, int length) {
        this.parent = parent;
        this.length = length;
    }

    int parent() {
        return parent;
    }

    int length() {
        return length;
    }
}

class Path { // 存储最小路径
    private ParentLength[] pls;
    private Graph g; // 确定指定位置的节点是否被访问过和打印时使用

    Path(int size, int start, Graph g) {
        // 初始化最小路径数组，将所有最小路径的起点都置为start，并将路径长度置为INFINITY
        pls = new ParentLength[size];
        for (int i = 0; i < size; i++)
            pls[i] = new ParentLength(start, Graph.INFINITY);
        this.g = g;
    }

    // 根据新发现的路径调整最小路径
    void adjust(int from, int to, int length) {
        // 根据上一个节点的路径，计算出新的路径长度
        int newLength = pls[from].length() != Graph.INFINITY ? pls[from]
                .length() + length : length;
        // 如果到指定节点的新路径长度小于原来的最小路径，则更新到该节点的最小路径，和其父节点
        if (newLength < pls[to].length())
            pls[to] = new ParentLength(from, newLength);
    }

    int getMin() { // 求得到当前所有未访问节点的最近的一个节点
        int pos = 0;
        for (int i = 1; i < pls.length; i++)
            if (!g.isVisited(i) && pls[i].length() < pls[pos].length())
                pos = i;
        return pos;
    }

    void print() { // 打印
        for (int i = 0; i < pls.length; i++) {
            int current = i;
            System.out
                    .print((pls[current].length() == Graph.INFINITY ? "INFINITY"
                            : pls[current].length())
                            + "  ");
            do {
                System.out.print(g.get(current) + " <-- ");
                current = pls[current].parent();
            } while (current != pls[current].parent());
            System.out.println(g.get(current));
        }
    }
}

class Vertex { // 顶点,记载数据value，并记载是否访问过
    private Object value;
    private boolean isVisited;

    Vertex(Object value) {
        this.value = value;
    }

    void visit() {
        isVisited = true;
    }

    void clean() {
        isVisited = false;
    }

    boolean isVisited() {
        return isVisited;
    }

    Object value() {
        return value;
    }

    @Override
    public String toString() {
        return "" + value;
    }
}

INFINITY  [0,0](0) <-- [0,0](0)
3  [0,1](3) <-- [0,0](0)
3  [0,2](2) <-- [1,1](1) <-- [0,0](0)
9  [0,3](6) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
7  [0,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
8  [0,5](1) <-- [0,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
2  [1,0](2) <-- [0,0](0)
1  [1,1](1) <-- [0,0](0)
8  [1,2](7) <-- [1,1](1) <-- [0,0](0)
5  [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
10  [1,4](5) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
10  [1,5](3) <-- [0,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
2  [2,0](1) <-- [1,1](1) <-- [0,0](0)
7  [2,1](6) <-- [1,1](1) <-- [0,0](0)
4  [2,2](3) <-- [1,1](1) <-- [0,0](0)
7  [2,3](3) <-- [2,2](3) <-- [1,1](1) <-- [0,0](0)
7  [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
11  [2,5](4) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
3  [3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
3  [3,1](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
8  [3,2](5) <-- [3,1](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
11  [3,3](7) <-- [2,2](3) <-- [1,1](1) <-- [0,0](0)
10  [3,4](3) <-- [2,3](3) <-- [2,2](3) <-- [1,1](1) <-- [0,0](0)
8  [3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
4  [4,0](1) <-- [3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
12  [4,1](9) <-- [3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
12  [4,2](9) <-- [3,1](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
16  [4,3](8) <-- [3,2](5) <-- [3,1](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
10  [4,4](2) <-- [3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
13  [4,5](5) <-- [3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
5  [5,0](1) <-- [4,0](1) <-- [3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
13  [5,1](9) <-- [4,0](1) <-- [3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
14  [5,2](2) <-- [4,1](9) <-- [3,0](1) <-- [2,0](1) <-- [1,1](1) <-- [0,0](0)
19  [5,3](9) <-- [4,4](2) <-- [3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
12  [5,4](2) <-- [4,4](2) <-- [3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)
10  [5,5](0) <-- [4,4](2) <-- [3,5](1) <-- [2,4](2) <-- [1,3](2) <-- [0,2](2) <-- [1,1](1) <-- [0,0](0)

版版学java多久了？

记不清了……我是上学的时候学的，一周上一天

哦，从小培养的啊，那你入门以后看什么书来提高的？

版版你好样的，你是通过看什么书来提高编程的呢？？？

版版你新年快乐啊！你的QQ是多少呢？？？我的QQ：254443912   加起我的QQ，向你学习一下啊！！！

厉害