迷宫 2D 递归算法死胡同问题

Question

我一直在试图做一个程序，可以递归地解决一个迷宫(应该适用于任何迷宫)。该算法的大部分递归是有效的，但是当迷宫检查死胡同和重新路由以找到解决方案(终点)的方法时，代码就不起作用了。我已经尝试了多种方法来调试，但它没有让我走远；我要么得到StackOverflowError，要么算法返回一个位置。

注意2D阵列的“字符指示符”：

• '*' = 墙壁
• '#' = 开始
• “$” = 结束
• ' ' = 可能的路径/不是墙
• “@” = 路径
• “~” = 死胡同

期望输出:

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

Maze solution:

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

以下是仅回溯一个位置的代码：

在这个版本中，我试图在找到一个可以回溯的位置后递归调用，并返回那个位置来回溯并找到解决方案

import java.util.*;
public class mazeOG {
    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
            
            // 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
                }

            // 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 - 1][col] == '@' && 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 - 1][col] != '#') {// if west 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 there's no way out, that means there is no solution
                    System.out.println("No Solution");              
                    return mazeArr;
                }
                
            return mazeArr;
        }
    }
}

此版本的输出：

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

Maze solution:
No Solution

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

以下是获取StackOverflowerr的版本的代码：

在这个版本中，我删除了代码中按位置追溯并递归调用的部分，相反，我只是指出该位置是一个死胡同，并递归调用算法来搜索下一个位置。

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

            // 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
            }

            //code from here and below is for the case of a dead end
            if (mazeArr[row][col] != '#' && isPath == false) {
                mazeArr[row][col] = '~'; // indicates that this index is a dead end
                isPath = true;
                isSolved = false;
                return algorithm(mazeArr, row, col, isSolved);
            }

            if (isPath == false) { // if there's no way out, that means there is no solution
                System.out.println("No Solution");
                return mazeArr;
            }

            return mazeArr;
        }
    }
}

任何帮助都会非常好！谢谢你：）

编辑：修改代码

public static void main(String[] args) {
        int row = 0, col = 0;
        char[][] mazeArr = { { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
                { '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
                { '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
                { '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
                { '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
                { '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
                { '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
                { '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10

        System.out.println("Input maze:");
        displayMaze(mazeArr, row, col);

        System.out.println("\nMaze solution:");
        boolean isSolved = algorithm(mazeArr);
        if (isSolved) {
            displayMaze(mazeArr, row, col);
        } else {
            System.out.println("No Solution");
        }
    }
    
    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
                //displays maze without dead end indicators
                if(mazeArr[row][col] == '~') {
                    //mazeArr[row][col] = ' ';
                }
                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
        }
    }
    
    
    //indicates starting point for the maze to start solving and recursively calls algorithm method that is overloaded
    //pre: char 2D array mazeArr
    //post: returns a boolean value from the overloaded algorithm method 
    public static boolean algorithm(char[][] mazeArr) {
        int row = 1, col = 1; // where maze starts
            return algorithm(mazeArr, row, col);
    }
    
    //solves the maze looking for a solution (if there is one), modifies the 2D array accordingly 
    //to the algorithm to trace the solution
    //pre: char 2D array mazeArr, int row and col
    //post: returns boolean value depending on the algorithms solution
    public static boolean algorithm(char[][] mazeArr, int row, int col) {
        
        if (mazeArr[row][col] == '$') { // found the target/exit
            return true; //maze is completely solved 
        }
        
        if (mazeArr[row][col] == ' ') { // if there is a path
            mazeArr[row][col] = '@'; //mark as visited, block off path to not go back here again
        } 
        
        else if (mazeArr[row][col] != '#') { // not allowed
            return false;
        }
        // the core of the algorithm: try each direction until true is returned
        
        if (algorithm(mazeArr, row, col - 1) // west
                || algorithm(mazeArr, row - 1, col) // north
                || algorithm(mazeArr, row, col + 1) // east
                || algorithm(mazeArr, row + 1, col) // south
        ) {
            return true; // path found
        }
        
        if (mazeArr[row][col] == '@') { // mark backtracking
            mazeArr[row][col] = '~'; // indicates that this index is a dead end
        }
        
        return false;
        
    }

Answer 1

有几个问题，包括：

>

死端不应触发新的递归调用。死区标记应该在从递归回溯时发生，并且应该向调用方指示没有成功。

检查某个方向（北，…等）的每个if语句将在其块中执行返回，这意味着如果存在这样的方向，则不会尝试任何其他方向。

由于递归调用不返回是否成功，调用者无法知道是否应该尝试另一个方向

不是问题，而是：

• 还有相当多的代码重复，你应该避免。
• 没有充分的理由使显示函数递归。只需使用两个 for 循环遍历单元格
• 避免在主程序中使用行和 col 变量：这些变量应该在那里没有业务。
• 当你改变迷宫时，应该没有必要也返回那个迷宫。呼叫者将以任何方式访问填充的迷宫后调用。
• 将起点 （#） 的搜索与算法的其余部分分开时，代码将更容易。

函数成功的关键之一是返回一个布尔值，指示是否找到了路径。这样，算法可以决定是否应该在另一个方向上重试。

以下是对代码的修改：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        char[][] mazeArr = { 
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
                { '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
                { '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
                { '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
                { '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
                { '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
                { '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
                { '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10

        System.out.println("Input maze:");
        displayMaze(mazeArr);
        
        System.out.println("\nMaze solution:");
        boolean isSolved = algorithm(mazeArr);
        if (isSolved) {
            displayMaze(mazeArr);
        } else {
            System.out.println("No Solution");
        }
    }

    public static void displayMaze(char[][] mazeArr) {
        for (char[] row : mazeArr) {
            for (char cell : row) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
    }

    public static boolean algorithm(char[][] mazeArr) {
        // Look for starting point
        for (int row = 0; row < mazeArr.length; row++) {
            for (int col = 0; col < mazeArr[0].length; col++) {
                if (mazeArr[row][col] == '#') {
                    return algorithm(mazeArr, row, col);
                }
            }
        }
        return false; // No starting point found
    }

    public static boolean algorithm(char[][] mazeArr, int row, int col) {
        if (mazeArr[row][col] == '$') { // Found the target
            return true;
        }
        if (mazeArr[row][col] == ' ') {
            mazeArr[row][col] = '@'; // Mark as visited
        } else if (mazeArr[row][col] != '#') { // Not allowed
            return false;
        }
        // The core of the algorithm: try each direction until true is returned
        if (algorithm(mazeArr, row, col - 1) // west
                || algorithm(mazeArr, row - 1, col) // north
                || algorithm(mazeArr, row, col + 1) // east
                || algorithm(mazeArr, row + 1, col) // south
        ) {
            return true; // Path found
        }
        if (mazeArr[row][col] == '@') { // mark backtracking
            mazeArr[row][col] = '~';
        }
        return false;
    }
}

从评论中我了解到您不想使用循环。在这种情况下，使用递归在单独的递归函数中查找起始单元格，并将找到的点作为单个整数返回（row*width col）。

下面是相应的代码：

public class Main {
    public static void main(String[] args) {
        char[][] mazeArr = { 
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
                { '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
                { '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
                { '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
                { '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
                { '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
                { '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
                { '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10

        System.out.println("Input maze:");
        displayMaze(mazeArr);
        
        System.out.println("\nMaze solution:");
        boolean isSolved = algorithm(mazeArr);
        if (isSolved) {
            displayMaze(mazeArr);
        } else {
            System.out.println("No Solution");
        }
    }

    public static void displayMaze(char[][] mazeArr) {
        displayMaze(mazeArr, 0, 0); // add the arguments
    }
    
    public static void displayMaze(char[][] mazeArr, int row, int col) {
        if (row >= mazeArr.length) {
            return; // all done
        }
        if (col >= mazeArr[0].length) {
            System.out.println();
            displayMaze(mazeArr, row + 1, 0);
        } else {
            System.out.print(mazeArr[row][col] + " ");
            displayMaze(mazeArr, row, col + 1);
        }
    }

    public static int findStart(char[][] mazeArr, int i) {
        // Look for starting point. i is combination of row/col
        int row = i / mazeArr.length;
        if (row >= mazeArr.length) {
            return -1; // all done, and not found
        }
        int col = i % mazeArr[0].length;
        if (mazeArr[row][col] == '#') {
            return i; // found it
        }
        return findStart(mazeArr, i + 1);
    }

    public static boolean algorithm(char[][] mazeArr) {
        int i = findStart(mazeArr, 0);
        if (i == -1) {
            return false; // No starting point found
        }
        int row = i / mazeArr.length;
        int col = i % mazeArr[0].length;
        return algorithm(mazeArr, row, col);
    }

    public static boolean algorithm(char[][] mazeArr, int row, int col) {
        if (mazeArr[row][col] == '$') { // Found the target
            return true;
        }
        if (mazeArr[row][col] == ' ') {
            mazeArr[row][col] = '@'; // Mark as visited
        } else if (mazeArr[row][col] != '#') { // Not allowed
            return false;
        }
        // The core of the algorithm: try each direction until true is returned
        if (algorithm(mazeArr, row, col - 1) // west
                || algorithm(mazeArr, row - 1, col) // north
                || algorithm(mazeArr, row, col + 1) // east
                || algorithm(mazeArr, row + 1, col) // south
        ) {
            return true; // Path found
        }
        if (mazeArr[row][col] == '@') { // mark backtracking
            mazeArr[row][col] = '~';
        }
        return false;
    }
}