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

Question

我一直在尝试制作一个可以递归解决迷宫的程序（应该为任何迷宫起作用）。该算法的大部分递归均起作用，但是当迷宫检查死胡同以及重新路由以找到解决方案（终点）时，代码不起作用。我已经尝试了多种调试方法，但还没有让我走得更远。我要么得到StackoverFlowerRor，要么该算法可以通过一个位置回溯。

注释2D数组：

• '*'= walls
• '= start
• '$'= end
• '=可能路径/不是墙
• '@'@'=路径
• '〜'=死胡同

所需的输出：

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

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

这是获得stackoverflowerror的版本的代码：

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

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

有几个问题，包括：

• 死胡同不应触发新的递归电话。递归中的回溯时，应进行死端标记，并应向呼叫者表明没有成功。

  
  

• 如果 语句检查某个方向（北等），则将在其块中执行返回，这意味着如果有这样方向都不会尝试其他方向。

• 由于递归呼叫都不会返回，无论是否有成功，呼叫者都无法知道它是否应该在另一个方向上尝试

而不是问题，而是：

• 也有很多代码重复，您应该避免。
• 没有充分的理由使显示功能递归。只需用两个循环在单元格上迭代
• 行和col 变量：这些变量应在那里没有业务。
• 当您突变迷宫时，应该也不需要返回迷宫。呼叫者将在通话后如何访问填充的迷宫。
• 当您将搜索起点（＃）与其他算法的其余部分分开时，代码将变得更容易。

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

这是您的代码的修改：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        char[][] mazeArr = { 
                { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
                { '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
                { '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
                { '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
                { '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
                { '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
                { '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
                { '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
                { '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '
没有
我了解您不想使用循环的评论的循环。在这种情况下，使用递归在单独的递归函数中查找起始单元，并将发现的位置返回单个整数（ 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) {
        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] == '
没有
我了解您不想使用循环的评论的循环。在这种情况下，使用递归在单独的递归函数中查找起始单元，并将发现的位置返回单个整数（ row*width + 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 ）。
这是相应的代码：

, '*' }, // 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] == '
, '*' }, // 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] == '
没有
我了解您不想使用循环的评论的循环。在这种情况下，使用递归在单独的递归函数中查找起始单元，并将发现的位置返回单个整数（ row*width + 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）。

这是相应的代码：

) { // 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; } } , '*' }, // 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] == '

没有

我了解您不想使用循环的评论的循环。在这种情况下，使用递归在单独的递归函数中查找起始单元，并将发现的位置返回单个整数（row*width + 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）。

这是相应的代码：