DFS迷宫寻路算法在大尺寸矩阵下出现栈溢出问题求助

核心问题拆解 #

1. 边界检测逻辑隐患：原代码用maze[1].length判断x的边界，当迷宫行数小于2时直接触发索引越界，这也是移除边界检测后错误频发的根源。
2. 墙的处理关联问题：路径碰到墙时的异常，本质是边界检测错误导致非法索引访问，被误判为墙相关问题。
3. 大矩阵栈溢出：递归DFS依赖JVM栈空间，默认栈容量无法支撑250x250及更大矩阵的深度递归，导致栈溢出。

针对性修复方案 #

1. 修复边界检测逻辑 #

将边界判断顺序调整为先校验y的合法性，再校验x的合法性，避免访问不存在的行索引；同时用当前行的长度判断x的范围，适配可能的不规则行（尽管迷宫一般是矩形，但逻辑更严谨）：

public static boolean searchPath(int[][] maze, int x, int y, ArrayList<Integer> path) {
    // 先确保y在合法行范围内，再判断x是否在当前行的列范围内
    if (y < 0 || y >= maze.length || x < 0 || x >= maze[y].length) {
        return false;
    }
    if (maze[y][x] == 9) {
        path.add(x);
        path.add(y);
        return true;
    }
    // 仅处理可走路径（0），墙/已访问节点直接返回false
    if (maze[y][x] == 0) {
        maze[y][x] = 2; // 标记为已访问，避免重复遍历

        // 用数组统一管理四个方向，简化代码
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] dir : directions) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            if (searchPath(maze, newX, newY, path)) {
                path.add(x);
                path.add(y);
                return true;
            }
        }
    }
    return false;
}

2. 解决大矩阵栈溢出问题 #

递归DFS的深度受限于JVM栈大小（默认一般仅支持几千层递归），大矩阵下必须改用迭代DFS，用堆内存中的栈模拟递归过程，彻底摆脱栈深度限制：

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class MazeSolver {
    public static boolean searchPathIterative(int[][] maze, int startX, int startY, ArrayList<Integer> path) {
        // 栈中存储坐标数组，以及该节点是否已完成子节点遍历
        Stack<Pair<int[], Boolean>> stack = new Stack<>();
        stack.push(new Pair<>(new int[]{startX, startY}, false));
        // 记录每个节点的父节点，用于找到目标后回溯路径
        Map<String, int[]> parentMap = new HashMap<>();

        while (!stack.isEmpty()) {
            Pair<int[], Boolean> current = stack.pop();
            int x = current.getKey()[0];
            int y = current.getKey()[1];
            boolean processed = current.getValue();

            // 边界校验
            if (y < 0 || y >= maze.length || x < 0 || x >= maze[y].length) {
                continue;
            }

            // 找到目标点，回溯路径
            if (maze[y][x] == 9) {
                path.add(x);
                path.add(y);
                int[] prev = parentMap.get(x + "," + y);
                while (prev != null) {
                    path.add(prev[0]);
                    path.add(prev[1]);
                    prev = parentMap.get(prev[0] + "," + prev[1]);
                }
                // 回溯路径是从目标到起点，反转后得到起点到目标的顺序
                Collections.reverse(path);
                return true;
            }

            // 已处理过的节点直接跳过
            if (processed) {
                continue;
            }

            // 墙/已访问节点跳过
            if (maze[y][x] != 0) {
                continue;
            }

            // 标记为已访问
            maze[y][x] = 2;
            // 重新压入已处理标记的节点，确保子节点遍历完成后再处理当前节点
            stack.push(new Pair<>(new int[]{x, y}, true));

            // 注意栈是后进先出，为了和递归顺序一致，反转方向顺序
            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            for (int[] dir : directions) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                parentMap.put(newX + "," + newY, new int[]{x, y});
                stack.push(new Pair<>(new int[]{newX, newY}, false));
            }
        }
        // 未找到路径
        return false;
    }

    // 自定义Pair类，避免依赖javafx
    static class Pair<K, V> {
        private final K key;
        private final V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

修复效果说明 #

• 边界检测修复后，移除顶部检测代码的索引越界问题彻底解决，墙相关异常也会消失
• 迭代DFS版本可稳定处理任意尺寸的矩阵，不会出现栈溢出问题
• 代码结构更简洁，方向遍历用数组统一管理，可读性和可维护性提升

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