在二维数组最短路径 [英] Shortest path in 2d arrays

问题描述

*...*..D
.G..*.....
**...**.
.S....*.
........
...G**..
........
.G..*...

下面是二维数组的地方
S-来源
D-目标
G点一定要参观
。自由路径
*阻止路径
你能帮助我这将是有效的算法找到最短伯提的长度在Java中
只有水平和垂直运动是possiable

Here is 2d array where
S- Source
D-Destination
G-Point must be visited
." . "Free paths
"*"Block Paths
Can you help me which would be the efficient algorithm to find the length of shortest pathi in java
Only Horizontal and Vertical movements are possiable

推荐答案

要找到从的最短距离启动指向地图中所有其他的点，你可以使用 BFS 。 样品code：

To find the shortest distance from start point to all other points in the map, you can use a BFS. Sample code:

public void visit(String []map , Point start){
        int []x = {0,0,1,-1};//This represent 4 directions right, left, down , up
        int []y = {1,-1,0,0};
        LinkedList<Point> q = new LinkedList();
        q.add(start);
        int n = map.length;
        int m = map[0].length();
        int[][]dist = new int[n][m];
        for(int []a : dist){
            Arrays.fill(a,-1);
        }
        dist[start.x][start.y] = 0;
        while(!q.isEmpty()){
            Point p = q.removeFirst();
            for(int i = 0; i < 4; i++){
                int a = p.x + x[i];
                int b = p.y + y[i];
                if(a >= 0 && b >= 0 && a < n && b < m && dist[a][b] == -1 && map[a].charAt(b) != '*' ){
                    dist[a][b] = 1 + dist[p.x][p.y];
                    q.add(new Point(a,b));
                }
            }
        }
    }

这个问题的第二条路径实际上是一个旅行商问题，所以你需要转换从原始图形的曲线图中只有G，D和S点，与重量中的每个边缘这个图是在原路径之间的最短路径。从那以后，如果G数小（小于17），可以使用动态规划和掩码来解决这个问题。

The second path of the problem is actually a traveling salesman problem, so you need to convert from your original graph to a graph which only contains G,D and S points, with the weight of each edge in this graph is the shortest path between them in original path. From that onward, if the number of G is small (less than 17) you can use dynamic programming and bitmask to solve the problem.

这篇关于在二维数组最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！