java - 作业任务——通过int方法回溯

Question

以下代码旨在将您从 [0,0] 带到 [a.length-1][a[0].length-1]通过最快路线的二维阵列。规则是您只能向左\右\上\下前进，并且下一个单元格必须大于(大于)当前单元格。

    private static int path(int[][]a,int i, int j, int count)
    {
        if((i==a.length-1)&&(j==a[0].length-1))
            return count+1;
        if((j<a[0].length-1)&&(a[i][j]<a[i][j+1]))
            if(canPass(a,i,j+1))
                return (path(a,i,j+1,count+1));
        if((i<a.length-1)&&(a[i][j]<a[i+1][j]))
            if(canPass(a,i+1,j))
                return path(a,i+1,j,count+1);
        if((i>0)&&(a[i][j]<a[i-1][j]))
            if(canPass(a,i-1,j))
                return path(a,i-1,j,count+1);
        if((j>0)&&(a[i][j]<a[i][j-1]))
            if(canPass(a,i,j-1))
                return path(a,i,j-1,count+1);
         return -1;
private static boolean canPass(int[][]a,int i,int j)
    {
        if((i==a.length-1)&&(j==a[0].length-1))
            return true;
        if((j<a[0].length-1)&&(a[i][j]<a[i][j+1]))
                 if(canPass(a,i,j+1))
                    return true;
         if((i<a.length-1)&&(a[i][j]<a[i+1][j]))
                 if(canPass(a,i+1,j))
                    return true;
         if((i>0)&&(a[i][j]<a[i-1][j]))
                 if(canPass(a,i-1,j))
                    return true;
         if((j>0)&&(a[i][j]<a[i][j-1]))
                 if(canPass(a,i,j-1))
                    return true;
         return false;
        }
public static void main(String args[])//DRIVER
    {    
       int[][] multi = new int[][]{
  { 3, 13, 15, 28, 30 },
  { 40, 51, 52, 29, 30 },
  { 28, 10, 53, 54, 53 },
  { 53, 12, 55, 53, 60 },
  { 70, 62, 56, 20, 80 },
  { 80, 81, 90, 95, 100 },
};
System.out.println(path(multi));   

这段代码有效。但是，有两件事我不满意，希望得到您的帮助:

1. 方法末尾的 return -1 行 - 它本质上从未被调用过吗？我怎样才能避免它？

2. boolean 方法的使用 - 我尝试仅使用 int 方法进行回溯，但找不到解决方案。

谢谢!

Answer 1

这里的递归实现可能需要一些工作，..或者更少的工作!

在 canPass 函数中，您可以对网格进行整个递归评估。您在这里完成了所有必要的工作来找到有效的路径。如果路径是可能的，那么您可以在 path 函数中移动一个 block ，并忘记您所做的所有工作。在下一步中，您将再次重新评估整个网格。这是太多的工作，并且随着网格大小的增加，您的实现将变得非常慢。

理想情况下，对于这个程序，您只需要一个递归函数。 canPass 函数应该只是告诉您下一个方 block 是否可能。它确实只是存在，因此您不必连续写出条件 4 次。如果没有可能的路径，则返回 -1 以表明它无效。并且不要将计数传递给其他函数，只需在返回时增加计数即可。

这是一个示例方法:

public static boolean canPass(int[][]a, int i, int j, int oldValue){
    if((j >= a[0].length) || (j < 0) || (i >= a.length) || (i < 0)){
        return false;
    }
    return a[i][j] > oldValue;
}

// added a helper function to reduce repetitive code
public static int chooseShortest(int nextPath, int currentPath){
    if (nextPath != -1){
        if (currentPath == -1 || currentPath > nextPath){
                return nextPath;
            }
        }
    }
    return currentPath;
}

public static int path(int[][]a, int i, int j)
{
    // This is the end condition
    // there is one step left so return 1
    if((i == a.length - 1) && (j==a[0].length - 1)){
        return 1;
    }

    int shortestPath = -1;

    if (canPass(a, i, j + 1, a[i][j])){
        shortestPath = chooseShortest(path(a, i, j + 1), shortestPath);
    }
    if (canPass(a, i, j - 1, a[i][j])){
        shortestPath = chooseShortest(path(a, i, j - 1), shortestPath);
    }
    if (canPass(a, i + 1, j, a[i][j])){
        shortestPath = chooseShortest(path(a, i + 1, j), shortestPath);
    }
    if (canPass(a, i - 1, j, a[i][j])){
        shortestPath = chooseShortest(path(a, i - 1, j), shortestPath);
    }
    // if all 4 paths return -1 there is no path possible from here
    if (shortestPath == -1){
        return -1;
    }

    // return the shortest path + 1 step to get there
    return shortestPath + 1;
}