递归方法查找矩阵中的路径数 [英] recursive method finding number of paths in a matrix

问题描述

我写了一种方法，可以计算从二维数组中给定单元格到给定目标单元格的路径数，但是由于某种原因，它返回错误的答案，有什么想法吗?

i have wrote a method that calculates number of paths from a given cell in a 2-dimension array, to a given destination cell, but for some reason it returns an incorrect answer, any thoughts?

   private static int numParths(int [][] mat, int x1, int y1, int x2, int y2)
    {
        if(x1<0  ||  x1 >mat.length-1 || y1<0  ||  y1>mat.length-1)
          return 0;


        if(x1 == x2 && y1 == y2){
        System.out.println("1"); 
          return 1;
        }


        if(mat[x1][y1]==-1)
          return 0;

          mat[x1][y1]=-1;
          return numParths(mat, x1, y1+1, x2, y2) + numParths(mat, x1-1, y1, x2, y2) + numParths(mat, x1+1, y1, x2, y2) + numParths(mat, x1, y1-1, x2, y2);
    }

    public static void main (String[]args){
        int [][] mat={{1,2,3,4},{1,2,3,4},{1,2,3,4},{1,2,3,4}};
        System.out.println(numParths(mat, 0,1,2,3));
    }

推荐答案

使用递归和一些干净"的代码可以解决这类问题.但是，最好先在常规递归基础上构建一个解决方案，然后看看是否可以使用动态编程以提高效率. 关于这个特定问题，我们可以通过将已计算的信息(从参考点到目标点的路径数)存储在变量中来重新使用它.另一个尺寸相似的矩阵在这里对我们很有用(因为我们可能不想更改输入矩阵).

These kind of problems can be solved using Recursion with some "clean looking" code. However, it is better to first build a solution on top of general recursion and see if you can use Dynamic Programming in order to be efficient. Regarding this particular problem, we can re-use already calculated information (number of paths from the reference point to the destination point) by storing it in variables. Another matrix with similar dimensions would be good for us here (as we may not want to change the input matrix).

以下是几种解决方案:

1. 普通递归方法(从效率方面不推荐)

1. Normal Recursive Approach (Not recommended in terms of efficiency)

//Call to a recursive method numPathsRecursive. There is no need of passing matrix array, just source and destination points are sufficient.

int numPaths(int[][] matrix, int x, int y, int X, int Y){
   return numPathsRecursive(x,y,X,Y); 
}


int numPathsRecursive(int x, int y, int X, int Y){// x and y are Source co ordinates; X and Y are destination co ordinates
    if (x==X && y==Y){
        return 1;
    }
    else if (x>X || y>Y){//Boundary Conditions possible (Right part of Matrix & Bottom part of Matrix)
        return 0;
    }
   return numPathsRecursive(x+1,y,X,Y) + numPathsRecursive(x,y+1,X,Y);
}

基于动态编程的方法(我们基本上在此之上基于上述递归方法)

Dynamic Programming Based Approach (We basically build on top of the above recursive approach here)

int numPaths(int[][] matrix, int x, int y, int X, int Y){
   int countMatrixRows = X-x+1;
   int countMatrixColumns = Y-y+1;
   int[][] countMatrix = new int[countMatrixRows][countMatrixColumns];// initialising count matrix which stores number of paths from each point to the end point of the count Matrix (i.e., destination of original matrix)
    for (int i=0;i<countMatrixRows;i++){//Initialisation of countMatrix with -1s
        for (int j=0;j<countMatrixColumns;j++){
            countMatrix[i][j]=-1;
        }
    }
    countMatrix[countMatrixRows-1][countMatrixColumns-1]=1; //Setting destination cell value as 1. (indicating there's one path to itself)
    return numPathsDP(countMatrix,0,0,countMatrixRows-1,countMatrixColumns-1); //Call to numPathsDP. Now the original problem boils down to finding path from 0,0 of countMatrix to countMatrixRows-1,countMatrixColumns-1
}

int numPathsDP(int[][] countMatrix, int x, int y, int X, int Y){
    if (x>X || y>Y){
        return 0;
    }
    if (countMatrix[x][y]==-1){
        countMatrix[x][y]=numPathsDP(countMatrix,x+1,y,X,Y)+numPathsDP(countMatrix,x,y+1,X,Y); //It's indeed a recursive function but we are storing the result value in the same 2d array
    }
    return countMatrix[x][y]; // It will return 1 when destination cell is reached the first time. The same returned value will be used to add up when called from other cells (See above line)
}

假设:

1. 仅允许您在右侧和底部进行遍历，如果还有其他可能的路径，则只需要在索引上调用具有适当操作的方法即可.例如，如果还允许对角线，那么您需要添加其他方法调用

1. You are allowed to traverse only on your right and bottom, if there are other possible paths, just you need to call the method with appropriate operation on index. For example, if diagonal is also allowed, then you need to add additional method invocation

numPathsDP(countMatrix,x+1,y+1,X,Y)

总结一下.即总和为

 countMatrix[x][y]=numPathsDP(countMatrix,x+1,y,X,Y)+numPathsDP(countMatrix,x,y+1,X,Y)+numPathsDP(countMatrix,x+1,y+1,X,Y) 

在DP解决方案中.

1. 可以从源单元格到达目标单元格，并且源单元格和目标单元格都被封装在原始矩阵中(基于矩阵的尺寸)

这篇关于递归方法查找矩阵中的路径数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！