Java递归回溯迷宫求解：程序停滞与数组越界异常排查

你遇到的无限循环和数组越界问题，其实是递归回溯迷宫求解中很常见的几个坑，我帮你拆解下原因，再给你修复后的完整代码：

问题根源分析 #

1. 无限循环：你大概率没有做「避免走回头路」的处理——比如刚从左边走到当前位置，递归时又立刻尝试走回左边，导致在两个位置之间反复调用递归，陷入死循环。
2. 数组越界（-1）：边界判断的顺序错了！比如你先检查maze[row][col]是否合法，再判断row或col是否小于0，这会导致当row=-1时直接访问数组，触发异常。
3. 回溯不彻底：如果递归失败后没有把标记的x恢复成原来的通路状态，会导致后续路径判断错误，甚至阻断正确路径。

修复后的完整代码 #

下面是修正后的程序，包含每一步的标记、打印和回溯逻辑：

public class MazeSolver {
    // 迷宫定义：#=墙，.=通路，S=起点，E=终点
    private static char[][] maze = {
            {'S', '.', '#', '.', '.'},
            {'#', '.', '#', '#', '.'},
            {'.', '.', '.', '#', '.'},
            {'#', '#', '.', '.', '.'},
            {'#', '#', '#', '#', 'E'}
    };
    private static int totalRows = maze.length;
    private static int totalCols = maze[0].length;

    public static void main(String[] args) {
        System.out.println("=== 初始迷宫 ===");
        printMaze();
        if (solveMaze(0, 0)) {
            System.out.println("\n✅ 成功找到路径！");
        } else {
            System.out.println("\n❌ 迷宫没有可行路径！");
        }
    }

    private static boolean solveMaze(int currentRow, int currentCol) {
        // 1. 先判断是否到达终点
        if (maze[currentRow][currentCol] == 'E') {
            System.out.println("\n=== 到达终点！最终迷宫状态 ===");
            printMaze();
            return true;
        }

        // 2. 严格检查当前坐标合法性：先判断是否越界，再判断是否是墙/已标记的路径
        if (currentRow < 0 || currentRow >= totalRows 
            || currentCol < 0 || currentCol >= totalCols 
            || maze[currentRow][currentCol] == '#' 
            || maze[currentRow][currentCol] == 'x') {
            return false;
        }

        // 3. 标记当前位置为已尝试路径
        char originalChar = maze[currentRow][currentCol];
        maze[currentRow][currentCol] = 'x';
        System.out.println("\n=== 尝试位置：(" + currentRow + "," + currentCol + ") ===");
        printMaze();

        // 4. 尝试四个方向：上、下、左、右（顺序可调整，不影响结果）
        boolean foundPath = solveMaze(currentRow - 1, currentCol)  // 上
                        || solveMaze(currentRow + 1, currentCol)  // 下
                        || solveMaze(currentRow, currentCol - 1)  // 左
                        || solveMaze(currentRow, currentCol + 1); // 右

        // 5. 回溯：如果四个方向都走不通，恢复当前位置的原始状态
        if (!foundPath) {
            maze[currentRow][currentCol] = originalChar;
            System.out.println("\n=== 回溯位置：(" + currentRow + "," + currentCol + ") ===");
            printMaze();
        }

        return foundPath;
    }

    // 打印当前迷宫状态
    private static void printMaze() {
        for (char[] row : maze) {
            for (char cell : row) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
    }
}

关键修复点说明 #

• 边界检查顺序：先判断currentRow < 0或currentCol < 0，再访问数组，彻底杜绝-1索引的越界异常。
• 避免回头路：递归判断时直接排除已标记的x，不会重复走已经尝试过的路径，解决无限循环问题。
• 完整回溯：用originalChar保存当前位置的原始值，递归失败后恢复，确保回溯时正确移除x，不影响后续路径尝试。
• 直观的过程展示：每一步标记、回溯都打印迷宫状态，清晰看到程序的尝试过程。

额外调试建议 #

如果你想自定义迷宫，只需要修改maze二维数组即可；如果起点不是(0,0)，调整main函数中solveMaze的调用参数就行。另外，可以在递归函数中打印当前调用栈，更方便追踪递归流程。

内容的提问来源于stack exchange，提问作者jacobay43