Нахождение кратчайшего пути в лабиринте с координатами - PullRequest
Новая
       34

Нахождение кратчайшего пути в лабиринте с координатами

0 голосов
/ 07 января 2019

Эй, я новичок, я написал программу, которая ищет кратчайший путь от начала до конца в 2-мерном массиве. Но моя проблема в том, что я не могу найти полный путь с координатами. Я имею в виду, например, что: 

  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)

Это мой метод для этого, я пытаюсь сделать это с помощью списка, но до сих пор не знаю, как это сделать и как правильно очистить их во время процесса (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;

1 Ответ

0 голосов
/ 07 января 2019

Так как вы хотели путь, я изменил тип вашего метода returnty и внес некоторые незначительные изменения: 

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;
}
...