Java迷宫问题排查：栈溢出错误及Bcopy矩阵未更新问题

现有代码问题排查 #

1. 陌生人视野标记错误 #

你的原始视野标记逻辑存在两个核心错误：

• 未处理障碍物遮挡逻辑：陌生人的视野会被障碍物X阻断，不能直接将朝向方向的整行/整列全部标记为禁行
• 遍历顺序冲突：你按从左到右、从上到下的顺序遍历格子，还未遍历到后方的X/其他箭头时就提前标记了可通行状态，导致部分禁行区域被覆盖为可通行
• 未考虑特殊位置优先级：箭头本身、障碍物的禁行优先级高于空地，初始位置A需要单独标记为可通行

2. 栈溢出错误 #

递归逻辑存在多处致命问题：

• 边界检查顺序错误：先访问数组元素再判断索引是否越界，会触发数组越界异常，且你原来的终止条件j==copy[0].length本身属于越界值，逻辑错误
• 参数传递错误：使用i++/j++/i--/j--传递参数，后自增/自减会先传原始值再修改当前方法的变量值，导致后续递归的参数全错，甚至出现来回往复调用的情况
• 未标记已访问路径：走过的格子没有标记为已访问，会出现同一条路径来回递归的死循环，最终触发栈溢出
• 未使用短路或：使用按位或|而非短路或||，即使已经找到可行路径，仍然会执行所有剩余递归，严重浪费栈空间

修复后代码 #

import java.util.*;

class Solution {
    // 四个方向：上下左右
    private static final int[][] DIRS = {{-1,0}, {1,0}, {0,-1}, {0,1}};

    public boolean solution(String[] B) {
        int rows = B.length;
        int cols = B[0].length();
        int[][] Bcopy = new int[rows][cols];
        int rowA = -1;
        int colA = -1;

        // 第一步：先标记所有障碍物、箭头的固定禁行位置，记录A的坐标
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char c = B[i].charAt(j);
                if (c == 'A') {
                    rowA = i;
                    colA = j;
                } else if (c == 'X' || c == '^' || c == 'v' || c == '<' || c == '>') {
                    // 障碍物和陌生人本身都是禁行区域
                    Bcopy[i][j] = -1;
                }
            }
        }

        // 第二步：单独标记所有陌生人的视野，碰到障碍物就停止标记
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char c = B[i].charAt(j);
                if (c == '>') {
                    for (int k = j+1; k < cols; k++) {
                        if (B[i].charAt(k) == 'X') break; 
                        Bcopy[i][k] = -1;
                    }
                } else if (c == '<') {
                    for (int k = j-1; k >= 0; k--) {
                        if (B[i].charAt(k) == 'X') break;
                        Bcopy[i][k] = -1;
                    }
                } else if (c == 'v') {
                    for (int k = i+1; k < rows; k++) {
                        if (B[k].charAt(j) == 'X') break;
                        Bcopy[k][j] = -1;
                    }
                } else if (c == '^') {
                    for (int k = i-1; k >= 0; k--) {
                        if (B[k].charAt(j) == 'X') break;
                        Bcopy[k][j] = -1;
                    }
                }
            }
        }

        // 初始位置本身就在禁行区直接返回失败
        if (Bcopy[rowA][colA] == -1) return false;

        // 递归遍历所有路径，默认出口为迷宫右下角
        return helper(Bcopy, rowA, colA, rows, cols);
    }

    private boolean helper(int[][] copy, int i, int j, int rows, int cols) {
        // 先做边界校验，越界直接返回失败
        if (i < 0 || i >= rows || j <0 || j >= cols) return false;
        // 校验是否为禁行区或已经访问过
        if (copy[i][j] == -1) return false;
        // 终止条件：走到右下角，可根据实际需求调整出口判断规则
        if (i == rows -1 && j == cols -1) return true;

        // 标记当前格子已访问，避免重复走导致死循环
        copy[i][j] = -1;

        // 四个方向遍历，用短路或，找到可行路径就直接返回
        return helper(copy, i+1, j, rows, cols)
                || helper(copy, i-1, j, rows, cols)
                || helper(copy, i, j+1, rows, cols)
                || helper(copy, i, j-1, rows, cols);
    }
}

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