Проблема с рекурсивным алгоритмом Maze 2D

Я пытался сделать программу, которая могла бы рекурсивно решать лабиринт. Но у меня проблема с моей рекурсией в моем методе алгоритма. Алгоритм может решить только одну позицию для решения.

Вот это на консоли:

Обратите внимание на «символьные индикаторы» для 2D-массива:

  • '*' = стены
  • '#' = начало
  • '$' = конец
  • ' ' = возможный путь/не стена
  • '@' = путь
  • '~' = тупик

Желаемый результат:

Presolved maze:
* * * * * * * * * * 
* # * * * * * * * * 
*   *           * * 
*   *       *   * * 
*       *   *   * * 
* * *       *   * * 
* *     *   *   * * 
* *     *   *     * 
* * * * * * *     * 
*               $ * 
* * * * * * * * * * 

Maze solution:

* * * * * * * * * * 
* # * * * * * * * * 
* @ * @ @ @ @ @ * * 
* @ * @ ~ ~ * @ * * 
* @ @ @ * ~ * @ * * 
* * * ~ ~ ~ * @ * * 
* * ~ ~ * ~ * @ * * 
* * ~ ~ * ~ * @ ~ * 
* * * * * * * @ ~ * 
* ~ ~ ~ ~ ~ ~ @ $ * 
* * * * * * * * * *

Вывод, который я получаю:

Presolved maze:
* * * * * * * * * * 
* # * * * * * * * * 
*   *           * * 
*   *       *   * * 
*       *   *   * * 
* * *       *   * * 
* *     *   *   * * 
* *     *   *     * 
* * * * * * *     * 
*               $ * 
* * * * * * * * * * 

Maze solution:

* * * * * * * * * * 
* # * * * * * * * * 
* @ *           * * 
*   *       *   * * 
*       *   *   * * 
* * *       *   * * 
* *     *   *   * * 
* *     *   *     * 
* * * * * * *     * 
*               $ * 
* * * * * * * * * *

Я пробовал другие решения, такие как удаление рекурсии внутри рекурсии в моем общем случае, но это просто регрессировало незначительный прогресс, который мог сделать мой алгоритм (то есть найти одну позицию). Мне было интересно, что еще я мог бы сделать вместо этого, чтобы решить эту проблему? Другие методы работают, но метод «алгоритм» работает не так, как хотелось бы.

import java.util.*;
public class maze {
    public static void main(String[] args) {
        allocateMaze();
    }
    
    public static void allocateMaze() {
        char[][] mazeArr = {{'*','*','*','*','*','*','*','*','*','*'},//0
                            {'*','#','*','*','*','*','*','*','*','*'},//1
                            {'*',' ','*',' ',' ',' ',' ',' ','*','*'},//2
                            {'*',' ','*',' ',' ',' ','*',' ','*','*'},//3
                            {'*',' ',' ',' ','*',' ','*',' ','*','*'},//4
                            {'*','*','*',' ',' ',' ','*',' ','*','*'},//5
                            {'*','*',' ',' ','*',' ','*',' ','*','*'},//6
                            {'*','*',' ',' ','*',' ','*',' ',' ','*'},//7
                            {'*','*','*','*','*','*','*',' ',' ','*'},//8
                            {'*',' ',' ',' ',' ',' ',' ',' ','$','*'},//9
                            {'*','*','*','*','*','*','*','*','*','*'}};//10
        
        //setting row and col to 0 for display method
        int row = 0;
        int col = 0;
        System.out.println("Presolved maze:");
        displayMaze(mazeArr, row, col); //displays presolved maze
        row = 1;
        col = 1;
        boolean isSolved = false;
        System.out.println("\nMaze solution:");
        algorithm(mazeArr, row, col, isSolved); //create variable for solved maze, sends maze allocation to method that solves the maze
        System.out.println();
        row = 0;
        col = 0;
        displayMaze(mazeArr, row, col); //displays traced + solved maze
    }

    public static void displayMaze(char[][] mazeArr, int row, int col) {
        if (row < mazeArr.length) { //iterate through all (11) rows
            if (col < mazeArr[row].length) { //iterate through all (11) columns
                System.out.print(mazeArr[row][col] + " "); //displays the current index in the array
                displayMaze(mazeArr, row, col+1); //repeats this method by iterating through the columns first
                return;
            }
            System.out.println(); //enters the line after each row for display purposes
            displayMaze(mazeArr, row+1, col=0); //repeats this method by iterating through the rows
        }
    }
    
    public static char[][] algorithm(char[][] mazeArr, int row, int col, boolean isSolved){
        boolean isPath = false; // assume there is no path

        if (mazeArr[row][col] == '$' && isSolved == true) { // IF MAZE IS COMPLETELY SOLVED
            return mazeArr;

        } else { // IF MAZE IS NOT COMPLETELY SOLVED
            
            if (isSolved == false && isPath == false) { // start searching thru the maze, assume there is no path
                // THERE IS NO DEAD END
                
                if (mazeArr[row - 1][col] == ' ') { // if north has a path
                    mazeArr[row - 1][col] = '@'; // block off path to not go back here again
                    isPath = true; // there is a path
                    isSolved = false; // assume maze is still not solved
                    
                    return algorithm(mazeArr, row--, col, isSolved); // repeat process going to next north spot
                }
                
                if (mazeArr[row][col + 1] == ' ') { // if east has a path
                    mazeArr[row][col + 1] = '@'; // block off path to not go back here again
                    isPath = true; // there is a path
                    isSolved = false; // assume maze is still not solved

                    return algorithm(mazeArr, row, col++, isSolved); // repeat process going to next east spot
                }
                
                if (mazeArr[row + 1][col] == ' ') { // if south has a path
                    mazeArr[row + 1][col] = '@'; // block off path to not go back here again
                    isPath = true; // there is a path
                    isSolved = false; // assume maze is still not solved
                    
                    return algorithm(mazeArr, row++, col, isSolved); // repeat process going to next south spot
                }
                
                if (mazeArr[row][col - 1] == ' ') { // if west has a path
                    mazeArr[row][col - 1] = '@'; // block off path to not go back here again
                    isPath = true; // there is a path
                    isSolved = false; // assume maze is still not solved
                    
                    return algorithm(mazeArr, row, col--, isSolved); // repeat process going to next west spot
                }
                
                if (mazeArr[row][col] == '$') { // if you have reached the end of the maze
                    isSolved = true; // maze has been solved
                    
                    
                    return algorithm(mazeArr, row, col, isSolved); // algorithm will recognize
                }

            } else { // finds alternate path if there's a dead end
                if (mazeArr[row][col] != '#') {
                mazeArr[row][col] = '~'; //indicates that this index is a dead end
                }
                
                if (isPath == false) {
                    if (mazeArr[row - 1][col] == '@' && mazeArr[row - 1][col] != '#') { // if north was a path
                        isPath = true; 
                        isSolved = false;
                        
                        return algorithm(mazeArr, row--, col, isSolved); //returns to initial position before hitting dead end
                    }
                }
                
                if (isPath == false) {
                    if (mazeArr[row][col+1] == '@' && mazeArr[row][col+1] != '#') { // if east was a path
                        isPath = true; 
                        isSolved = false;
                        
                        return algorithm(mazeArr, row, col++, isSolved); //returns to initial position before hitting dead end
                    }
                }
                
                if (isPath == false) {
                    if (mazeArr[row + 1][col] == '@' && mazeArr[row + 1][col] != '#') { // if south was a path
                        isPath = true; 
                        isSolved = false;
                        
                        return algorithm(mazeArr, row++, col, isSolved); //returns to initial position before hitting dead end
                    }
                }
                
                if (isPath == false) {
                    if (mazeArr[row][col-1] == '@' && mazeArr[row][col-1] != '#') { // if west was a path
                        isPath = true; 
                        
                        return algorithm(mazeArr, row, col--, isSolved); //returns to initial position before hitting dead end
                    }
                }
                
                if (isPath == false) { // if there's no way out, that means there is no solution
                    System.out.println("No Solution");              
                    return mazeArr;
                }
                
            }
            return mazeArr;
        }
    }
}

Вы пытались отладить программу, чтобы увидеть, где она идет не так?

Just another Java programmer 10.04.2022 08:06

Я думаю, что isPath это неправильная логика. Можете ли вы объяснить, что это такое?

Neil 10.04.2022 08:06

@Neil isPath используется, чтобы указать, есть ли путь или нет, он позволяет алгоритму понять, нет ли пути, идущего NESW, чтобы алгоритм мог проверить тупиковую часть кода, отсюда и условие (isSolved == false && isPath == false). если isPath все еще остается ложным внутри рекурсии в рекурсии, что означает, что путь, который проходил алгоритм, был тупиковым, он переходит к структуре else, которая находит путь назад из тупика.

anon 10.04.2022 20:09
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
2
3
34
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вам нужно поставить ++ или -- перед row или col, когда вы вспоминаете algorithm(). Когда один из них идет после переменной, переменная увеличивается, но не выходное значение:

public class Test {
    public static void main(String[] args) {
        int x = 5;
        int y = x++;
        System.out.println(x + " " + y);
    }
}

дает

6 5

Выше x++ увеличилось x, но y раньше было установлено значение x. Чтобы исправить это, поместите инкремент перед переменной, например ++row:

public class Test {
    public static void main(String[] args) {
        int x = 5;
        int y = ++x;
        System.out.println(x + " " + y);
    }
}

выход:

6 6

Другие вопросы по теме