使用 DP 递归方法的地牢问题

问：

这是个问题...... 以下问题围绕着一个冒险家展开，他进入地牢寻找黄金 （宝藏）。所有问题的目标都是找到通往黄金的最快途径 不会给冒险家带来伤害。在每个问题中，我们将编辑或引入新元素 到地牢（地下牢房）。你的任务是找到最短的路径 冒险家获得黄金，黄金可以位于地牢的任何地方。（位置 黄金将在输入中给出）。 在每个回合中，冒险者（去地牢里拿金子的人）都可以移动 一步（向右、向左、向上、向下）。冒险家和金币都可以占据单个单元格 （即单元格中可以有任意数量的项目） 地牢中将引入一个怪物（M）。怪物的目的是阻止冒险家 从获得黄金开始。它将以最好的方式移动以实现这一目标（即如果怪物可以 在冒险者之前达到金币，那么怪物可以阻止冒险者获得 黄金）。只有在冒险者采取行动后，怪物才会移动。 注意：-

1. 怪物可能会也可能不会每回合移动（每次冒险者移动时）。
2. 怪物和冒险家都知道对方的位置。 任务：找到最小的步数，这样冒险者就可以在不死亡的情况下到达黄金。

示例输入 1： 地牢尺寸（行x列）：5 4 冒险者的位置：4 1 怪物的位置：3 1 黄金位置：2 3 示例输出 1： 没有可能的解决方案 示例输入 2： 地牢尺寸（行x列）：5 4 冒险家的位置：5 1 怪物的位置：3 1 黄金位置：4 3 示例输出 2： 最小步数：3

我尝试了 dp 递归方法，但我不知道出了什么问题？对于某些输入，我收到StackOverflow错误，对于某些输入，我没有得到正确的输出。这是我下面的 JAVA 代码。

包装样品;

在线 Java 编译器

使用此编辑器在线编写、编译和运行 Java 代码 导入 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);
    }
    }
}