这就是问题... 以下问题围绕一名进入地牢寻找黄金的冒险家展开 （宝藏）。所有问题的目标都是找到通往黄金的最快路径 不会给冒险者带来伤害。在每个问题中，我们都会编辑或引入新元素 到地牢（地下牢房）。你的任务是找到最短路径 冒险家获得的黄金可以位于地牢的任何地方。 （位置 黄金将在输入中给出）。 在每个回合中，冒险家（去地牢中获取黄金的人）可以移动 一步（右、左、上、下）。一个单元格可以同时被冒险家和金币占据 （即单元格中可以有任意数量的项目） 地牢中将引入怪物（M）。怪物的目的是阻止冒险者 从获得黄金开始。它将以尽可能最好的方式移动来实现这一目标（即，如果怪物可以 在冒险家之前达到金币，那么怪物就可以阻止冒险家获得金币 金子）。只有冒险者行动后，怪物才会行动。 注意：-
示例输入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);
}
}
}
您的解决方案似乎走在正确的轨道上，但由于您如何低效地终止递归调用，因此密切关注诸如 StackOverflow 之类的错误始终很重要。
我首先将 Math.pow(10, 8) 替换为 Integer.MAX_VALUE 来表示无穷大。
if (a1 < 0 || a2 < 0 || m1 < 0 || m2 < 0 || a1 >= m || m1 >= m || a2 >= n || m2 >= n) {
return Integer.MAX_VALUE;
}
然后通过分别考虑冒险者和怪物的位置来改变处理冒险者和怪物移动的方式。
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int minSteps = Integer.MAX_VALUE;
for (int i = 0; i < 4; i++) {
int newA1 = a1 + dx[i];
int newA2 = a2 + dy[i];
int newM1 = m1;
int newM2 = m2;
if (newA1 == newM1 && newA2 == newM2) {
// If adventurer and monster collide, the monster doesnt move
newM1 = m1;
newM2 = m2;
} else {
// Monster tries to move closer to adventurer
int dxMonster = (a1 - m1) > 0 ? 1 : (a1 - m1) < 0 ? -1 : 0;
int dyMonster = (a2 - m2) > 0 ? 1 : (a2 - m2) < 0 ? -1 : 0;
newM1 = m1 + dxMonster;
newM2 = m2 + dyMonster;
}
int steps = 1 + findMinSteps(m, n, newA1, newA2, newM1, newM2, g1, g2, dp);
minSteps = Math.min(minSteps, steps);
}
我还将输入索引修改为从 0 开始，因为 Java 中的所有数组都遵循这一惯例。
int result = findMinSteps(m, n, a1 - 1, a2 - 1, m1 - 1, m2 - 1, g1 - 1, g2 - 1, dp);
将上述所有内容与其余内容添加在一起后：
import java.util.*;
public class DungeonSolver {
public static int findMinSteps(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 Integer.MAX_VALUE;
}
if (a1 == g1 && a2 == g2) {
return 0;
}
if (a1 == m1 && a2 == m2) {
return Integer.MAX_VALUE;
}
if (dp[a1][a2][m1][m2] != -1) {
return dp[a1][a2][m1][m2];
}
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int minSteps = Integer.MAX_VALUE;
for (int i = 0; i < 4; i++) {
int newA1 = a1 + dx[i];
int newA2 = a2 + dy[i];
int newM1 = m1;
int newM2 = m2;
if (newA1 == newM1 && newA2 == newM2) {
newM1 = m1;
newM2 = m2;
} else {
int dxMonster = (a1 - m1) > 0 ? 1 : (a1 - m1) < 0 ? -1 : 0;
int dyMonster = (a2 - m2) > 0 ? 1 : (a2 - m2) < 0 ? -1 : 0;
newM1 = m1 + dxMonster;
newM2 = m2 + dyMonster;
}
int steps = 1 + findMinSteps(m, n, newA1, newA2, newM1, newM2, g1, g2, dp);
minSteps = Math.min(minSteps, steps);
}
dp[a1][a2][m1][m2] = minSteps;
return minSteps;
}
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 = findMinSteps(m, n, a1 - 1, a2 - 1, m1 - 1, m2 - 1, g1 - 1, g2 - 1, dp);
if (result == Integer.MAX_VALUE) {
System.out.println("No possible solution");
} else {
System.out.println("Minimum number of steps: " + result);
}
}
}