java - 递归查找矩阵中的路径

Question

我正在尝试解决我正在学习的类(class)中的一个问题，找到包含数字的矩阵中的最长路径 - 数字之间存在特定的差异。

我有私有(private)方法来检查我可以朝哪个方向做，但现在我正在尝试找到斜坡的“深度”。

我为每次潜水保留一个 maxDepth 变量 - 如果它是最深的，则将其分配给“深度” - 由于某种原因，深度始终保持为 0。

private static int longestSlope(int[][] mat, int num, int i, int j, int depth, int maxDepth ){
        if (canUp(mat, num, i, j)) {
            maxDepth = longestSlope(mat, num, i - 1, j, depth, maxDepth + 1);
            if (depth < maxDepth) {
                depth = maxDepth;
            }
            maxDepth = 0;
        }
        if (canDown(mat, num, i, j)) {
            maxDepth = longestSlope(mat, num, i + 1, j, depth, maxDepth + 1);
            if (depth < maxDepth) depth = maxDepth;
            maxDepth = 0;
        }
        if (canRight(mat, num, i, j)) {
            maxDepth = longestSlope(mat, num, i, j + 1, depth, maxDepth + 1);
            if (depth < maxDepth) depth = maxDepth;
            maxDepth = 0;
        }
        if (canLeft(mat, num, i, j)) {
            maxDepth = longestSlope(mat, num, i, j - 1, depth, maxDepth + 1);
            if (depth < maxDepth) depth = maxDepth;
        }

        return depth;
    }


private static boolean canUp(int[][] mat, int num, int i, int j) {
    if (i == 0) {
        return false;
    } else if (mat[i - 1][j] == -1) {
        return false;
    } else if (mat[i][j] - mat[i - 1][j] != num) {
        return false;
    }
    return true;
}

Answer 1

在检查您是否可以向各个方向移动后，您将返回深度。当您到达无法向任何方向移动的点时，这会给您带来问题。由于深度在递归调用后更新，因此您的方法将返回 0，并且该值将在其父递归调用中分配给 maxDepth。当您到达无法在 4 个方向中的任何一个方向移动的点时，您需要进行基本情况检查。像这样的事情应该可以解决问题:

private static int longestSlope(int[][] mat, int num, int i, int j, int depth, int maxDepth ){
    if(canUp(mat, num, i, j) == false && canDown(mat, num, i, j) == false && canRight(mat, num, i, j) == false) && canDown(mat, num, i, j) == false) {
        // this means that you cannot move in any of the 4 directions: the base case
        return maxDepth;
    }
    if (canUp(mat, num, i, j)) {
        maxDepth = longestSlope(mat, num, i - 1, j, depth, maxDepth + 1);
        if (depth < maxDepth) {
            depth = maxDepth;
        }
        maxDepth = 0;
    }
    if (canDown(mat, num, i, j)) {
        maxDepth = longestSlope(mat, num, i + 1, j, depth, maxDepth + 1);
        if (depth < maxDepth) depth = maxDepth;
        maxDepth = 0;
    }
    if (canRight(mat, num, i, j)) {
        maxDepth = longestSlope(mat, num, i, j + 1, depth, maxDepth + 1);
        if (depth < maxDepth) depth = maxDepth;
        maxDepth = 0;
    }
    if (canLeft(mat, num, i, j)) {
        maxDepth = longestSlope(mat, num, i, j - 1, depth, maxDepth + 1);
        if (depth < maxDepth) depth = maxDepth;
    } 
    return depth;
}

为了将来的引用，确定递归函数中的基本情况并返回您正在计算的任何值始终是一个好主意。这样做将帮助您避免此类微妙的错误!