如何输出最短路径的方向？

Question

这是一个简单的迷宫求解器程序。

.0........
..........
.0...0.0.0
...0...0..
..........
.0.0......
.........0
...F....0.
..........
S.0...0...

这是我正在研究的简单迷宫。我实现了一个输出路径坐标的解决方案，如下所示。（从 BFS 算法获得的坐标）

Start - x = 9 y = 0
Move up to - x = 8 y = 0
Move up to - x = 7 y = 0
Move Right to - x = 7 y = 1
Move Right to - x = 7 y = 2
Move Right to - x = 7 y = 3
Finish

但我想输出如下（省略相同方向，只输出方向和最后一个坐标到相同方向），

Start        - x = 9 y = 0
Move up to   - x = 7 y = 0
Move Right to- x = 7 y = 3
Finish

这所有的坐标都分配给一个stack.below是我的代码，

System.out.println("Start - " + curr);
        curr = stack.pop();


        while (!stack.isEmpty()) {
            System.out.println(curr);
            curr = stack.pop();
        }
        System.out.println(curr);

    }

Answer 1

最简单的方法是定义一个接受两个坐标和 returns 方向的函数，然后遍历坐标并检查与下一个坐标相比是否有变化。

public static String getDirection(int x1, int y1, int x2, int y2) {
    if(x1 == x2 && y1 > y2)
        return "up";
    if(x1 == x2 && y1 < y2)
        return "down";
    if(y1 == y2 && x1 < x2)
        return "right";
    if(y1 == y2 && x1 > x2)
        return "left";
    return "undecidable";
}

// It is written so just for simplicity. 
// Use an array of Coord structs or something like that.
public static void printDirections(int[] x, int[] y) {
    System.out.printf("Start - x = %d y = %d\n", x[0], y[0]);

    String lastDirection = getDirection(x[0], y[0], x[1], y[1]);
    for(int i = 1; i < x.length - 1; i++) {
        String direction = getDirection(x[i], y[i], x[i + 1], y[i + 1]);
        if(!lastDirection.equals(direction)) {
            System.out.printf("Move %s to x = %d y = %d", lastDirection, x[i], y[i]);
        }

        lastDirection = direction;
    }
    System.out.printf("Move %s to x = %d y = %d", lastDirection, x[x.length - 1], y[y.length - 1]);
}

如何输出最短路径的方向？

How to output direction of shortest path?

java

algorithm

stack

output

breadth-first-search