地牢问题DP递归实现故障排查：栈溢出与结果错误

安全阿岳

2026-7-10

问题背景

地牢中有一名冒险者，目标是找到一条最短路径抵达黄金，过程中不能受到伤害。地牢规则如下：

每回合冒险者可向上下左右移动1步，同一单元格可同时容纳冒险者与黄金。
地牢中有怪物（M），会采取最优策略阻止冒险者获取黄金：若怪物比冒险者先到达黄金位置，就能阻止冒险者；怪物仅在冒险者移动后行动，每回合可选择移动或不移动。
冒险者与怪物互相知晓对方位置。
任务要求：找出冒险者安全抵达黄金的最少步数。

示例输入输出

示例输入1：
地牢尺寸（行×列）：5 4
冒险者位置：4 1
怪物位置：3 1
黄金位置：2 3
示例输出1：无可行解
示例输入2：
地牢尺寸（行×列）：5 4
冒险者位置：5 1
怪物位置：3 1
黄金位置：4 3
示例输出2：最少步数：3

用户问题

我尝试用DP递归方法解决这个问题，但遇到了两个问题：部分输入会触发栈溢出错误，部分输入的计算结果不正确。以下是我的Java代码，请帮忙排查问题：

package sample;

//Online Java Compiler
//Use this editor to write, compile and run your Java code online
import java.util.*;

public class HelloWorld {
public static int findminstep(int m, int n, int a1, int a2, int m1, int m2, int g1, int g2, int[][][][]       dp) {
    if (a1 < 0 || a2 < 0 || m1 < 0 || m2 < 0 || a1 >= m || m1 >= m || a2 >= n || m2 >= n) {
        return (int) Math.pow(10, 8);
    }

    if (a1 == g1 && a2 == g2) {
        return 0;
    }

    if (a1 == m1 && a2 == m2) {
        return (int) Math.pow(10, 8);
    }

    if (m1 == g1 && m2 == g2) {
        return (int) Math.pow(10, 8);
    }

    if (dp[a1][a2][m1][m2] != -1) {
        return dp[a1][a2][m1][m2];
    }

    int aa = 1 + findminstep(m, n, a1 - 1, a2, m1, m2, g1, g2, dp);
    int ab = 1 + findminstep(m, n, a1, a2 + 1, m1, m2, g1, g2, dp);
    int ac = 1 + findminstep(m, n, a1 + 1, a2, m1, m2, g1, g2, dp);
    int ad = 1 + findminstep(m, n, a1, a2 - 1, m1, m2, g1, g2, dp);
    int amin = Math.min(Math.min(aa, ab), Math.min(ac, ad));

    int ma = 1 + findminstep(m, n, a1 - 1, a2, m1 - 1, m2, g1, g2, dp);
    int mb = 1 + findminstep(m, n, a1 - 1, a2, m1, m2 + 1, g1, g2, dp);
    int mc = 1 + findminstep(m, n, a1 - 1, a2, m1 + 1, m2, g1, g2, dp);
    int md = 1 + findminstep(m, n, a1 - 1, a2, m1, m2 - 1, g1, g2, dp);

    int me = 1 + findminstep(m, n, a1, a2 + 1, m1 - 1, m2, g1, g2, dp);
    int mf = 1 + findminstep(m, n, a1, a2 + 1, m1, m2 + 1, g1, g2, dp);
    int mg = 1 + findminstep(m, n, a1, a2 + 1, m1 + 1, m2, g1, g2, dp);
    int mh = 1 + findminstep(m, n, a1, a2 + 1, m1, m2 - 1, g1, g2, dp);

    int mi = 1 + findminstep(m, n, a1 + 1, a2, m1 - 1, m2, g1, g2, dp);
    int mj = 1 + findminstep(m, n, a1 + 1, a2, m1, m2 + 1, g1, g2, dp);
    int mk = 1 + findminstep(m, n, a1 + 1, a2, m1 + 1, m2, g1, g2, dp);
    int ml = 1 + findminstep(m, n, a1 + 1, a2, m1, m2 - 1, g1, g2, dp);

    int mm = 1 + findminstep(m, n, a1, a2 - 1, m1 - 1, m2, g1, g2, dp);
    int mn = 1 + findminstep(m, n, a1, a2 - 1, m1, m2 + 1, g1, g2, dp);
    int mo = 1 + findminstep(m, n, a1, a2 - 1, m1 + 1, m2, g1, g2, dp);
    int mp = 1 + findminstep(m, n, a1, a2 - 1, m1, m2 - 1, g1, g2, dp);
    int bmin1 = Math.min(Math.min(ma, mb), Math.min(mc, md));
    int bmin2 = Math.min(Math.min(me, mf), Math.min(mg, mh));
    int bmin3 = Math.min(Math.min(mi, mj), Math.min(mk, ml));
    int bmin4 = Math.min(Math.min(mm, mn), Math.min(mo, mp));

    int bmin = Math.min(Math.min(bmin1, bmin2), Math.min(bmin3, bmin4));

    int res = Math.min(amin, bmin);
    dp[a1][a2][m1][m2] = res;

    return res;
}

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int m, n, a1, a2, m1, m2, g1, g2;
    System.out.println("Enter rows:");
    m = scan.nextInt();
    System.out.println("Enter Column");
    n = scan.nextInt();
    System.out.println("Enter Adventurer Position:");
    a1 = scan.nextInt();
    a2 = scan.nextInt();
    System.out.println("Enter Monster Position");
    m1 = scan.nextInt();
    m2 = scan.nextInt();
    System.out.println("Enter Gold Position");
    g1 = scan.nextInt();
    g2 = scan.nextInt();
    int dp[][][][] = new int[m][n][m][n];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                for (int l = 0; l < n; l++) {
                    dp[i][j][k][l] = -1;
                }
            }
        }
    }

    int result = findminstep(m, n, a1, a2, m1, m2, g1, g2, dp);

    if (result == (int) Math.pow(10, 8)) {
        System.out.println("No possible solution");
    } else {
        System.out.println("Minimum number of steps: " + result);
    }
    }
}

问题排查与修正

1. 栈溢出问题原因及解决

递归深度过大导致栈溢出。你的代码采用自顶向下的递归DP，当地牢尺寸较大时，递归调用栈会不断累积，超出JVM默认栈容量。

解决方法：改用迭代式的BFS（广度优先搜索），BFS天然适合寻找最短路径问题，且不会出现栈溢出；或者保留DP但改为自底向上的迭代实现。

2. 核心逻辑错误分析

你的递归逻辑完全不符合问题规则，主要错误点：

错误处理怪物的最优策略：怪物会选择让冒险者无法到达黄金的路径（即对冒险者的每一步移动，怪物会选择最坏情况），但你代码中却对怪物的所有可能移动取最小值，这完全颠倒了逻辑。
遗漏怪物可以不移动的规则，代码中只考虑了怪物移动的情况。
终止条件顺序错误：应该先判断冒险者是否到达黄金（成功），再判断是否被怪物追上或怪物先到黄金（失败）。

3. 修正后的代码（BFS实现）

package sample;

import java.util.*;

public class HelloWorld {
    static class State {
        int ax, ay;
        int mx, my;
        int steps;

        State(int ax, int ay, int mx, int my, int steps) {
            this.ax = ax;
            this.ay = ay;
            this.mx = mx;
            this.my = my;
            this.steps = steps;
        }
    }

    public static int findMinStep(int rows, int cols, int startAx, int startAy, int startMx, int startMy, int goldX, int goldY) {
        // 方向数组：上下左右 + 不移动（怪物可选）
        int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}, {0,0}};
        // 已访问状态：ax, ay, mx, my
        boolean[][][][] visited = new boolean[rows][cols][rows][cols];
        Queue<State> queue = new LinkedList<>();

        // 转换为0-based坐标（示例输入为1-based）
        startAx--; startAy--;
        startMx--; startMy--;
        goldX--; goldY--;

        // 初始状态检查
        if (startAx == goldX && startAy == goldY) return 0;
        if (startAx == startMx && startAy == startMy) return -1;

        queue.add(new State(startAx, startAy, startMx, startMy, 0));
        visited[startAx][startAy][startMx][startMy] = true;

        while (!queue.isEmpty()) {
            State curr = queue.poll();

            // 第一步：冒险者移动
            for (int[] adir : dirs) {
                int newAx = curr.ax + adir[0];
                int newAy = curr.ay + adir[1];

                // 冒险者到达黄金，直接返回步数+1
                if (newAx == goldX && newAy == goldY) {
                    return curr.steps + 1;
                }

                // 冒险者移动出界，跳过
                if (newAx < 0 || newAx >= rows || newAy <0 || newAy >= cols) {
                    continue;
                }

                // 第二步：检查怪物是否能阻止冒险者
                boolean canProceed = true;
                Queue<int[]> monsterQueue = new LinkedList<>();
                boolean[][] monsterVisited = new boolean[rows][cols];
                monsterQueue.add(new int[]{curr.mx, curr.my});
                monsterVisited[curr.mx][curr.my] = true;

                while (!monsterQueue.isEmpty()) {
                    int[] mpos = monsterQueue.poll();
                    int mx = mpos[0], my = mpos[1];

                    // 怪物到达黄金，阻止冒险者
                    if (mx == goldX && my == goldY) {
                        canProceed = false;
                        break;
                    }

                    // 怪物追上冒险者
                    if (mx == newAx && my == newAy) {
                        canProceed = false;
                        break;
                    }

                    // 遍历怪物所有可能移动
                    for (int[] mdir : dirs) {
                        int newMx = mx + mdir[0];
                        int newMy = my + mdir[1];
                        if (newMx >=0 && newMx < rows && newMy >=0 && newMy < cols && !monsterVisited[newMx][newMy]) {
                            monsterVisited[newMx][newMy] = true;
                            monsterQueue.add(new int[]{newMx, newMy});
                        }
                    }
                }

                // 怪物无法阻止，且状态未访问过，加入队列
                if (canProceed && !visited[newAx][newAy][curr.mx][curr.my]) {
                    visited[newAx][newAy][curr.mx][curr.my] = true;
                    queue.add(new State(newAx, newAy, curr.mx, curr.my, curr.steps + 1));
                }
            }
        }

        // 所有路径尝试完毕，无可行解
        return -1;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter rows:");
        int rows = scan.nextInt();
        System.out.println("Enter Columns:");
        int cols = scan.nextInt();
        System.out.println("Enter Adventurer Position (x y):");
        int ax = scan.nextInt();
        int ay = scan.nextInt();
        System.out.println("Enter Monster Position (x y):");
        int mx = scan.nextInt();
        int my = scan.nextInt();
        System.out.println("Enter Gold Position (x y):");
        int gx = scan.nextInt();
        int gy = scan.nextInt();

        int result = findMinStep(rows, cols, ax, ay, mx, my, gx, gy);

        if (result == -1) {
            System.out.println("无可行解");
        } else {
            System.out.println("最少步数：" + result);
        }
    }
}

代码说明

采用BFS逐层搜索，确保找到的是最短路径
正确处理1-based到0-based的坐标转换（匹配示例输入格式）
严格模拟怪物的最优策略：只要怪物能到达黄金或追上冒险者，该路径就无效
记录已访问状态，避免重复搜索，提升运行效率

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

地牢问题DP递归实现故障排查：栈溢出与结果错误

示例输入输出 #

用户问题 #

问题排查与修正 #

1. 栈溢出问题原因及解决 #

2. 核心逻辑错误分析 #

3. 修正后的代码（BFS实现） #

代码说明 #