java - 用坐标寻找迷宫中的最短路径

Question

嘿，我是一个初学者，我编写了一个程序，该程序正在寻找二维数组中从开始到结束的最短路径。但我的问题是我找不到带有坐标的完整路径。我的意思是例如:

  public static void main(String[] args) {


    int[][] pom = new int[4][4];


    int arr[][] =
            {{0, 0, 0, 0, 0},
                    {0, 1, 1, 1, 0},
                    {0, 1, 1, 1, 1},
                    {0, 1, 1, 1, 1},
                    {0, 0, 1, 1, 1}};


    int startX = 3;
    int startY = 1;
    int endX = 2;
    int endY = 3;

    int min_dist = shortestPath(arr, pom, startX, startY, endX, endY, Integer.MAX_VALUE, 0);

    System.out.println(min_dist);

}

我想得到输出:(3,1),(3,2),(2,2),(2,3)

这是我的方法，我尝试使用 list 来做到这一点，但仍然不知道如何做到这一点以及如何在过程中正确清除它们 (Class Point 只有 2 个属性，int x 和 int y)

  static List<Point> tmp = new ArrayList<>();


public static boolean uCanGo(int mat[][], int visited[][], int x, int y) {

    if (mat[x][y] == 1 && visited[x][y] == 0) {
        //   tmp.add(new Point(x, y));

        return true;

    }


    return false;
}


public static int shortestPath(int arr[][], int visited[][], int startX, int startY, int endX, int endY, int finalDistance, int currentDistance) {
    if (startX == endX && startY == endY) {

        return Integer.min(finalDistance, currentDistance);

    }
    visited[startX][startY] = 1;



    if ((startY + 1 < 4) && uCanGo(arr, visited, startX, startY + 1)) {
        finalDistance = shortestPath(arr, visited, startX, startY + 1, endX, endY, finalDistance, currentDistance + 1);
    }
    if ((startX + 1 < 4) && uCanGo(arr, visited, startX + 1, startY)) {


        finalDistance = shortestPath(arr, visited, startX + 1, startY, endX, endY, finalDistance, currentDistance + 1);

    }
    if ((startX - 1 > 0) && uCanGo(arr, visited, startX - 1, startY)) {


        finalDistance = shortestPath(arr, visited, startX - 1, startY, endX, endY, finalDistance, currentDistance + 1);

    }
    if ((startY - 1 > 0) && uCanGo(arr, visited, startX, startY - 1)) {

        finalDistance = shortestPath(arr, visited, startX, startY - 1, endX, endY, finalDistance, currentDistance + 1);
    }
    visited[startX][startY] = 0;
    return finalDistance;
}

抱歉出现问题，谢谢

经过帮助，我仍然找不到问题，例如在该数组中应该有:(3,3)(4,3)(5,3)(6,3)(6,4)(6,5)

       int arr[][] =
                        {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                        {0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1},
                        {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1},
                        {0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0},
                        {0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0},
                        {0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1},
                        {0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0},
                        {0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1},
                        {0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1},
                        {0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1},
                        {0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1},
                };

        int startX = 3;
        int startY = 3;
        int endX = 6;
        int endY = 5;

Answer 1

由于您想要一条路径，因此我更改了方法的返回类型并做了一些小的更改:

public static void main(String[] args) {
    int arr[][] = { { 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 0 }, { 0, 1, 1, 1, 1 }, { 0, 1, 1, 1, 1 }, { 0, 0, 1, 1, 1 } };

    int startX = 3;
    int startY = 1;
    int endX = 2;
    int endY = 3;

    List<Point> path = new ArrayList<>();
    path.add(new Point(startX, startY));
    List<Point> foundPath = shortestPath(arr, startX, startY, endX, endY, Integer.MAX_VALUE, 0, path);

    for (Point p : foundPath) {
        System.out.print("(" + p.x + "," + p.y + "), ");
    }
    System.out.println();
}

public static boolean uCanGo(int mat[][], List<Point> visited, int x, int y) {
    if (mat[x][y] == 0) {
        return false;
    }
    for (Point p : visited) {
        if (p.x == x && p.y == y) {
            return false;
        }
    }
    return true;
}

public static List<Point> shortestPath(int arr[][], int startX, int startY, int endX, int endY, int finalDistance,
        int currentDistance, List<Point> visited) {
    if (startX == endX && startY == endY) {
        return visited;
    }

    if ((startY + 1 < 4) && uCanGo(arr, visited, startX, startY + 1)) {
        List<Point> nextPath = new ArrayList<>(visited);
        nextPath.add(new Point(startX, startY + 1));
        return shortestPath(arr, startX, startY + 1, endX, endY, finalDistance, currentDistance + 1, nextPath);
    }
    if ((startX + 1 < 4) && uCanGo(arr, visited, startX + 1, startY)) {
        List<Point> nextPath = new ArrayList<>(visited);
        nextPath.add(new Point(startX + 1, startY));
        return shortestPath(arr, startX + 1, startY, endX, endY, finalDistance, currentDistance + 1, nextPath);

    }
    if ((startX - 1 > 0) && uCanGo(arr, visited, startX - 1, startY)) {
        List<Point> nextPath = new ArrayList<>(visited);
        nextPath.add(new Point(startX - 1, startY));
        return shortestPath(arr, startX - 1, startY, endX, endY, finalDistance, currentDistance + 1, nextPath);

    }
    if ((startY - 1 > 0) && uCanGo(arr, visited, startX, startY - 1)) {
        List<Point> nextPath = new ArrayList<>(visited);
        nextPath.add(new Point(startX, startY - 1));
        return shortestPath(arr, startX, startY - 1, endX, endY, finalDistance, currentDistance + 1, nextPath);
    }
    return visited;
}