| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1397 人关注过本帖
标题:求数组最小和路径
只看楼主 加入收藏
a287154777
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2010-10-30
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:9 
求数组最小和路径
求数组最小和路径。
给定数组:从左上角走到右下角,每次可以沿着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 编辑 ]
搜索更多相关主题的帖子: 百度 
2013-02-04 13:34
shellingford
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:19
帖 子:228
专家分:1348
注 册:2010-8-9
收藏
得分:5 
这是一个算法问题
8个方向都可以走的,例如
0 9 9
9 1 9
1 9 9
1 1 1

如果碰到这样的情况就要往左下走了,所以往上 往左也不是不可能
2013-02-04 14:26
清微御宇
Rank: 6Rank: 6
来 自:开封
等 级:侠之大者
威 望:2
帖 子:318
专家分:497
注 册:2012-1-15
收藏
得分:2 
挺有意思的有木有人贴下源码看看学习下啊?

Stay hungry , Stay foolish!
2013-02-05 14:49
shellingford
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:19
帖 子:228
专家分:1348
注 册:2010-8-9
收藏
得分:13 
回复 楼主 a287154777
程序代码:
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)
2013-02-05 18:39
清微御宇
Rank: 6Rank: 6
来 自:开封
等 级:侠之大者
威 望:2
帖 子:318
专家分:497
注 册:2012-1-15
收藏
得分:0 
回复 4楼 shellingford
版版学java多久了?

Stay hungry , Stay foolish!
2013-02-07 11:55
shellingford
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:19
帖 子:228
专家分:1348
注 册:2010-8-9
收藏
得分:0 
回复 5楼 清微御宇
记不清了……我是上学的时候学的,一周上一天
2013-02-07 13:53
清微御宇
Rank: 6Rank: 6
来 自:开封
等 级:侠之大者
威 望:2
帖 子:318
专家分:497
注 册:2012-1-15
收藏
得分:0 
回复 6楼 shellingford
哦,从小培养的啊,那你入门以后看什么书来提高的?

Stay hungry , Stay foolish!
2013-02-07 17:56
ywb254443912
Rank: 1
等 级:新手上路
帖 子:13
专家分:0
注 册:2013-1-17
收藏
得分:0 
版版你好样的,你是通过看什么书来提高编程的呢???
2013-02-14 13:31
ywb254443912
Rank: 1
等 级:新手上路
帖 子:13
专家分:0
注 册:2013-1-17
收藏
得分:0 
版版你新年快乐啊!你的QQ是多少呢???我的QQ:254443912   加起我的QQ,向你学习一下啊!!!
2013-02-14 13:33
SUXU19881102
Rank: 1
等 级:新手上路
帖 子:10
专家分:4
注 册:2013-2-27
收藏
得分:0 
厉害
2013-02-27 12:51
快速回复:求数组最小和路径
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.022106 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved