递归prince方法死锁时返回值错误问题排查与修复求助

需求背景 #

prince方法为无循环递归方法，规则如下：

• 王子仅可向东西南北四个方向移动（不可斜向），在屋顶间跳跃寻找恶棍。
• 值为-1的单元格是恶棍所在位置（数组中唯一负值）。
• 方法接收三个参数：drm（二维屋顶高度数组）、i（起始行索引）、j（起始列索引）。
• 跳跃需满足以下条件：
  • 目标屋顶与当前屋顶高度值相同；
  • 向下跳的高度差不超过2（如从5到3、2到0）；
  • 向上爬的高度差不超过1（如从3到4、0到1）。
• 方法需返回到达恶棍的最短路径长度，若陷入死锁则返回-1。

现有代码 #

public class Test {
    public static int prince(int[][] drm, int i, int j) {
        final int BEEN_HERE = Integer.MAX_VALUE;
        if (drm[i][j] == -1) {
            return 1;
        }
        int temp  = drm[i][j];
        drm[i][j] = BEEN_HERE;
        int north = Integer.MAX_VALUE, south = Integer.MAX_VALUE, east = Integer.MAX_VALUE, west = Integer.MAX_VALUE;
        if (i - 1 >= 0) {
            if(drm[i - 1][j]==temp||temp - drm[i-1][j]==2||Math.abs(temp - drm[i-1][j])==1 || drm[i-1][j]==-1)
                north = prince(drm, i - 1, j) + 1;
        }
        if (i + 1 < drm[0].length) {
            if(drm[i + 1][j]==temp||temp - drm[i + 1][j]==2||Math.abs(temp - drm[i + 1][j])==1 || drm[i + 1][j]==-1)
                south = prince(drm, i + 1, j) + 1;
        }
        if (j - 1 >= 0 ) {
            if(temp==drm[i][j-1] || temp - drm[i][j-1]==2||Math.abs(temp - drm[i][j-1])==1 || drm[i][j-1]==-1)
                west = prince(drm, i, j - 1) + 1;
        }
        if (j + 1 < drm.length) {
            if(temp==drm[i][j+1] || temp - drm[i][j+1]==2||Math.abs(temp - drm[i][j+1])==1 || drm[i][j+1]==-1)
                east = prince(drm, i, j + 1) + 1;
        }
        if(north==Integer.MAX_VALUE&&south==Integer.MAX_VALUE&&east==Integer.MAX_VALUE&&west==Integer.MAX_VALUE){
            return -1;
        }
        return Math.min(Math.min(north, south), Math.min(east, west));
    }
    public static void main(String[] args) {
        int[][] a = 
        {{2,0,1,2,3}
        ,{2,3,5,5,4},
         {8,-1,6,8,7},
         {3,4,7,2,4}
        ,{2,4,3,1,2}};
        System.out.println(prince(a, 4, 4));
    }
}

问题描述 #

从数组a的[4][4]位置出发时，王子实际陷入死锁，但方法返回1而非预期的-1，需提供修复思路。

测试用例 #

int[][] a = {
        {2,0,1,2,3},
        {2,3,5,5,4},
        {8,-1,6,8,7},
        {3,4,7,2,4},
        {2,4,3,1,2}
};
System.out.println(prince(a, 4, 4));

问题根源分析 #

1. 无效路径处理错误：当递归分支返回-1（表示该路径无法到达恶棍），代码直接执行+1操作，将无效路径转换为数值（如-1+1=0），导致最小值计算错误地将其视为有效路径，最终返回错误结果。
2. 边界判断逻辑错误：行索引边界使用了列长度drm[0].length，列索引边界使用了行长度drm.length，导致部分位置的合法性判断错误。
3. 路径长度定义错误：当前位置为恶棍时返回1，不符合路径长度的定义（到达自身的路径长度应为0）。

修复步骤 #

1. 修正边界判断

• 南向（south）行索引判断改为i + 1 < drm.length
• 东向（east）列索引判断改为j + 1 < drm[0].length

2. 正确处理无效路径

仅当递归返回有效路径长度（非-1）时，才执行+1操作并更新对应方向的路径长度，否则保持该方向为Integer.MAX_VALUE（标记为不可行）。

3. 修正路径长度定义

当前位置为恶棍时返回0，符合路径长度的逻辑。

4. 优化代码可读性

提取跳跃条件判断为单独方法，避免重复逻辑。

修复后的完整代码 #

public class Test {
    public static int prince(int[][] drm, int i, int j) {
        final int BEEN_HERE = Integer.MAX_VALUE;
        // 当前位置是恶棍，返回0（已到达，无需移动）
        if (drm[i][j] == -1) {
            return 0;
        }
        int temp = drm[i][j];
        // 标记当前位置已访问
        drm[i][j] = BEEN_HERE;
        int north = Integer.MAX_VALUE, south = Integer.MAX_VALUE, east = Integer.MAX_VALUE, west = Integer.MAX_VALUE;

        // 北向判断
        if (i - 1 >= 0) {
            int targetVal = drm[i-1][j];
            if (targetVal != BEEN_HERE && checkJumpValid(temp, targetVal)) {
                int res = prince(drm, i-1, j);
                if (res != -1) {
                    north = res + 1;
                }
            }
        }

        // 南向判断（修正行边界）
        if (i + 1 < drm.length) {
            int targetVal = drm[i+1][j];
            if (targetVal != BEEN_HERE && checkJumpValid(temp, targetVal)) {
                int res = prince(drm, i+1, j);
                if (res != -1) {
                    south = res + 1;
                }
            }
        }

        // 西向判断
        if (j - 1 >= 0) {
            int targetVal = drm[i][j-1];
            if (targetVal != BEEN_HERE && checkJumpValid(temp, targetVal)) {
                int res = prince(drm, i, j-1);
                if (res != -1) {
                    west = res + 1;
                }
            }
        }

        // 东向判断（修正列边界）
        if (j + 1 < drm[0].length) {
            int targetVal = drm[i][j+1];
            if (targetVal != BEEN_HERE && checkJumpValid(temp, targetVal)) {
                int res = prince(drm, i, j+1);
                if (res != -1) {
                    east = res + 1;
                }
            }
        }

        // 恢复当前位置原始值，避免污染原数组
        drm[i][j] = temp;

        // 计算有效路径的最小值
        int minPath = Math.min(Math.min(north, south), Math.min(east, west));
        return minPath == Integer.MAX_VALUE ? -1 : minPath;
    }

    // 封装跳跃条件判断逻辑
    private static boolean checkJumpValid(int currentHeight, int targetHeight) {
        if (targetHeight == -1) {
            return true;
        }
        int diff = currentHeight - targetHeight;
        // 同高度、向下跳差≤2、向上爬差=1
        return (diff == 0) || (diff >= 1 && diff <= 2) || (diff == -1);
    }

    public static void main(String[] args) {
        int[][] a = {
                {2,0,1,2,3},
                {2,3,5,5,4},
                {8,-1,6,8,7},
                {3,4,7,2,4},
                {2,4,3,1,2}
        };
        System.out.println(prince(a, 4, 4)); // 现在返回-1，符合预期
    }
}

内容的提问来源于stack exchange，提问作者УмиД Т.