Проблема понимания рекурсивного решения лабиринта с помощью «Разделяй и властвуй» - PullRequest
Новая
       57

Проблема понимания рекурсивного решения лабиринта с помощью «Разделяй и властвуй»

0 голосов
/ 24 апреля 2020

Я пытаюсь рекурсивно решить лабиринт, используя d & c для задания. Я прочитал, что такое алгоритм d & c, но у меня возникают проблемы с рекурсивным использованием его в моей программе. Я могу заставить программу распечатать лабиринт, показывающий, что программа прошла весь лабиринт, и распечатать выходные координаты, но я не могу заставить его показать только кратчайший правильный путь (вместо того, чтобы показывать, что он проходит через каждое место в лабиринте). У меня также есть проблема, когда он печатает как координаты выхода, так и начальную координату, а это не то, чего я хочу.

Любая помощь или советы будут с благодарностью. Я не ищу прямо «это то, как вы это делаете», а скорее попробуйте этот подход, иначе d & c действительно нужно использовать следующим образом.

Я также включил свой рекурсивный метод. Лабиринт состоит из доски 1 для границ, и все доступные пути - 0; когда 0 проверяется и перемещается, оно превращается в 2. 

public int RecursiveRead(int row, int column, int pathLength) {
        try {
        if (maze[row][column] == 1) {
            return -1;
        }

        if (maze[row][column] == 0) {
            maze[row][column] = 2;
            return 1 + (Math.min(Math.min(RecursiveRead(row + 1, column, pathLength + 1), RecursiveRead(row - 1, column, pathLength + 1)),
                    Math.min(RecursiveRead(row, column + 1, pathLength + 1), RecursiveRead(row, column - 1, pathLength + 1))));
        }
        } catch (ArrayIndexOutOfBoundsException e) {
            maze[row][column] = 2;
            System.out.println("Exit is: (" + row + ", " + column + ")");
        }

        return 1;
    }
public void MazeSolver() {
        if (RecursiveRead(1, 0, 0) == -1) {
            System.out.println("There is no exit");
            return;
        } else {

            try {
                FileWrite();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return;

РЕДАКТИРОВАТЬ: Уточненный Вопрос: мне интересно, как использовать разделяй и властвуй, чтобы рекурсивно найти кратчайший путь к выходу, или если выход не существует.

...