java 整数矩阵格网上的最短路径算法未返回预期值

fzsnzjdm  于 2023-01-07  发布在  Java
关注(0)|答案(1)|浏览(114)

我有一个作业要提交,我需要帮助,我会非常感激!!
我需要写一个方法来获取一个整数矩阵网格,其中包含0及以上的数字。矩阵中的1值是不同的,包含-1。该函数还获取矩阵中的起始x和y。
我需要编写一个递归函数,它可以找到从起始x,y到-1值的最短路径。您可以向上和向下"跳"到左"右"。从一个索引"跳"到另一个索引的条件是2对相减之间的绝对值是否为0、1或2

最短路径是4我不能使用while和for循环以及全局变量
函数签名应为:第一个月
多谢了!
下面是我的尝试:

package assignment1;

import java.util.*;

public class run {
    static Scanner reader = new Scanner(System.in);

    public static int shortestPath(int[][] drm, int i, int j) {

        if (drm.length == 0 || i >= drm.length || j >= drm.length || i < 0 || j < 0)
            return 0;

        if (i > 0 && j > 0 && i < drm.length - 1 && j < drm[i].length - 1) {
            if (drm[i][j - 1] == -1) {
                System.out.print("Got it! the target is on the left");
                return 2;
            }
            if (drm[i][j + 1] == -1) {
                System.out.print("Got it! the target is on the right");
                return 2;
            }
            if (drm[i - 1][j] == -1) {
                System.out.print("Got it! the target is up");
                return 2;
            }
            if (drm[i + 1][j] == -1) {
                System.out.print("Got it! the target is down");
                return 2;
            }
        }

        int temp = drm[i][j];
        int left = Integer.MAX_VALUE, right = Integer.MAX_VALUE, up = Integer.MAX_VALUE, down = Integer.MAX_VALUE;

        if (isValidJump(drm, i, j, i + 1, j)) {
            System.out.print("down ");
            drm[i][j] = Integer.MIN_VALUE;
            down = shortestPath(drm, i + 1, j) + 1;
        }
        if (isValidJump(drm, i, j, i, j + 1)) {
            System.out.print("right ");
            drm[i][j] = Integer.MIN_VALUE;
            right = shortestPath(drm, i, j + 1) + 1;
        }
        if (isValidJump(drm, i, j, i, j - 1)) {
            System.out.print("left ");
            drm[i][j] = Integer.MIN_VALUE;
            left = shortestPath(drm, i, j - 1) + 1;
        }
        if (isValidJump(drm, i, j, i - 1, j)) {
            System.out.print("up ");
            drm[i][j] = Integer.MIN_VALUE;
            up = shortestPath(drm, i - 1, j) + 1;
        }

        drm[i][j] = temp;

        return Math.min(Math.min(Math.min(up, down), left), right);
    }

    public static boolean isValidJump(int[][] drm, int i, int j, int m, int n) {
        if (m < drm.length && m >= 0 && n < drm.length && n >= 0 && drm[m][n] != Integer.MIN_VALUE) {
            int jump = drm[m][n] - drm[i][j];

            if (jump == 0 || jump == 1 || jump == -1 || jump == -2) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] drm = { { 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(shortestPath(drm, 0, 0));
    }

}

它应该返回4(最短路径)

dldeef67

dldeef671#

考虑到这是一门课,我建议你通知你的教授,你从这篇文章中得到了关于堆栈溢出的帮助。忽视这一点在大多数大学会被认为是学术上的不诚实。
第二件事是,正如David所建议的,这是一个学习如何使用调试器的好机会,这是一项在你的学术生涯和工程岗位上都非常有价值的技能。

您的代码

现在看看你的代码,它确实给出了你所提出的情况的解"4",这是正确的。问题是如果你改变输入,输出可能不会给出正确的答案。
这是因为编写的代码给出了它找到的第一个路径,而不是最短路径。
你的递归逻辑是合理的,基于这段代码,你看起来理解了递归的基础。你的问题是一个小的逻辑缺陷,当你递归调用你的函数时,你是如何屏蔽你的数据的。
你应该有解决这个问题所需的一切。如果你仍然有问题,请尝试使用调试器并检查你进行递归调用的区域。
溶液
我建议你在看下面的剧透之前先试着自己弄清楚这一点。
在进行递归调用的代码中,通过设置drm[i][j] = Integer.MIN_VALUE进行屏蔽,问题是在每次递归调用返回后,在测试下一次递归调用之前,没有使用drm[i][j] = temp将其设置回上一个值。现在的情况是,当你下一次调用isValidJump()时,它总是返回false,因为在你对这个迭代进行了第一次递归调用之后,drm[i][j]总是Integer.MIN_VALUE
如何修复:
在每次递归调用shortestPath()后立即放置drm[i][j] = temp

相关问题