如何在 JAVA 中使用递归 return 矩阵中的最长路径

Question

我正在尝试用递归来解决这个问题。
问题是：对于正整数的二维数组，我如何 return 最长路径（步数），以便最长路径的每个单元格中的值来自整数的降序序列以及每个单元格之间的差异cell 是给定的数字 (num)。
假设 n 是单元格的值，因此 (n - num) 是正数（非零）。
我不能使用任何循环（for、while、...等）

方法：

public static int longestPath(int matrix[][],int number){...
return(__overloading__);
}

例如:

int number=1;
int [][]matrix ;
       matrix = new int[][]{{8, 15, 20, 33, 35},
                           {60, 59, 58, 32, 31},
                           {59, 17, 57, 56, 55},
                           {55, 15, 13, 58, 16}};

     System.out.print(" longestPath= "+ longestPath(matrix, num));
   }

如果我们搜索最长的路径，差值数 = 1

1-在单元格matrix[0][3]中，路径长为3，该路径中的值为33 -> 32 -> 31，结束于矩阵[1][4]

2-在单元格matrix[1][0]中路径长为6，路径中的值为60 -> 59 -> 58 -> 57 - > 56 -> 55 以 matrix[2][4]

结尾

3-在单元格matrix[1][0]中路径长为2并且该路径中的值为60 -> 59以结尾矩阵[2][0]

所以该方法必须return最长的路径它的6

如果我们搜索最长的路径，差值数 = 2

1-在单元格matrix[2][1]中，路径长为3，该路径中的值为17 -> 15 -> 13，结束于矩阵[3][2]

方法必须return最长路径其3.

我的非工作代码：

public class CC {

    public static int longestPath (int arr[][] , int  num){
        return longestPath(arr,arr.length-1,arr[0].length-1,num,0);
    }

    public static int longestPath (int arr[][],int rows,int cols,int num,int max){
        System.out.println("==> longestPath() arr value=" + arr[rows][cols] + " rows:"+rows + " cols:"+cols + " max:"+max);
        if (cols ==0 && rows != 0  ){  
            cols = arr[0].length-1;
            rows--;
        }
        if (rows ==0  && cols==0 ){
            System.out.println("finish");
            return 0;
        }

        int steps = searchPath(arr,rows,cols,num,max);
        if (steps > max) max=steps;
        longestPath(arr,rows,cols-1,num,max);
        return max ;
    }

    public static int searchPath(int arr[][],int rows,int cols,int num ,int counter){ 
        System.out.println("searchPath() arr value=" + arr[rows][cols] + " rows:"+rows + " cols:"+cols);
        int left=1,right=1,up=1,down=1;

        if ((cols != 0) && arr[rows][cols] - num == arr[rows-1][cols]  ){ // checking up cell
            counter++;
            up = searchPath(arr,rows-1,cols,num,counter);

        }
        if ((rows != arr.length-1)   &&   arr[rows][cols] - num == arr[rows+1][cols] ){ // checking down cell
            counter++;
            down = searchPath(arr,rows+1,cols,num,counter);
            // return counter;
        }
        if ((cols != 0)  &&  arr[rows][cols] - num == arr[rows][cols-1]){ // checking left cell
            counter++;
            left = searchPath(arr,rows,cols-1,num,counter);
            //return counter;
        } 
        if ((cols != arr[0].length-1)   &&   arr[rows][cols] - num == arr[rows][cols+1]  ){ //checking right cell
            counter++;
            right = searchPath(arr,rows,cols+1,num ,counter);
            //return counter;
        } 

        if ((left > right) && (left > up)    && (left > down)) // if left cell is bigger than all other direction return left
            return left;
        if ((right > left) && (right > up)   && (right > down))
            return right;
        if ((down > up)    && (down > right) &&( down > left))
            return down;
        if ((up> down) && (up > right) && (up>left))
            return up;

        return 0;
    }

}

在编写代码时，我运行遇到了很多运行问题

我做错了什么？提前致谢

Answer 1

在发布的解决方案（以及问题中）中，您从左上角 (0,0) 开始遍历整个二维数组，并希望检查每个元素的邻居。
要检查所有邻居，检查右下邻居足以覆盖所有¹:

¹：如果您对向上或向左的下降路径感兴趣，则需要检查4方向。这是因为您的图形是有向的。例如，从左到右可能无效的路径，从右到左可能有效。

这样做可以简化代码，减少对邻居的重复测试。
另一种使代码更易于阅读、调试和维护的技术是将其分解为定义良好的小方法，例如：

private static boolean isValidAddress(int row, int col, int maxRow, int maxCol) {
    if(row < 0 || col < 0) return false;
    if(row >= maxRow || col >= maxCol) return false;
    return true;
}

尝试以下解决方案：

public class Main {

    //moving in two directions, right and down, is sufficient
    //to cover a whole matrix without visiting the same address twice

    public static void main(String[] args) {
        int delta= 1;
        int [][]matrix =  new int[][]{
                                     {8, 15, 20, 33, 35},
                                     {60, 59, 58, 32, 31},
                                     {59, 17, 57, 56, 55},
                                     {55, 15, 13, 58, 16}};
        System.out.print(" longest Path= "+ longestPath(matrix, delta));
    }

     public static int longestPath (int arr[][] , int delta){
            return longestPath(arr, 0, 0, delta , 0);
     }

     //check all matrix elements, keep longest path found
     public static int longestPath (int arr[][],int row,int col, int num, int max){

        int steps = searchPath(arr,row,col,num, 1); //Initial path length is always 1
        if (steps > max) {  max=steps;  }

        if (row == arr.length-1 && col == arr[row].length -1 )  return max;
        col ++;
        if(col == arr[row].length){//end of row exceeded
            row++;    //new row
            col = 0;  //first column
        }

        return longestPath(arr,row,col,num,max);
    }

    public static int searchPath(int arr[][],int row,int col,int num ,int pathLength){

        int[][] neighbors = getNeighbors(arr, row, col, num);
        int rightPath = 0 , downPath = 0;
        //right neighbor
        if(neighbors[0] != null){
            rightPath = searchPath(arr, neighbors[0][0], neighbors[0][1], num, pathLength+1);
        }

        //down neighbor
        if(neighbors[1] != null){
            downPath = searchPath(arr, neighbors[1][0], neighbors[1][1], num, pathLength+1);
        }

        int returnPath = Math.max(rightPath, downPath); //max return value 
        return Math.max(pathLength, returnPath) ; //max of path length and returned value 
    }

    //return neighbors with value smaller by delta
    //returned array[0] represents right neighbor row, col  or null
    //returned array[1] represents down  neighbor row, col  or null
    private static int[][] getNeighbors(int[][] arr, int row, int col, int delta) {

        //moving in two directions, right and down, is sufficient
        //to cover a whole matrix without visiting the same address twice

        int[][] neighbors = {null, null};
        //right neighbor
        int newCol = col +1;
        if(isValidAddress(row, newCol, arr.length, arr[0].length)){
            if(arr[row][col] - arr[row][newCol] == delta){
                neighbors[0] = new int[]{row, newCol};
            }
        }

        //down neighbor
        int newRow = row + 1 ;
        if(isValidAddress(newRow, col, arr.length, arr[0].length)){
            if(arr[row][col] - arr[newRow][col] == delta){
                neighbors[1] = new int[]{newRow, col};
            }
        }

        return neighbors;
    }

    private static boolean isValidAddress(int row, int col, int maxRow, int maxCol) {
        if(row < 0 || col < 0) return false;
        if(row >= maxRow || col >= maxCol) return false;
        return true;
    }
}

如何在 JAVA 中使用递归 return 矩阵中的最长路径

How to return the longest path in matrix using recursion in JAVA

java

recursion

matrix

path-finding

longest-path