recursive method finding number of paths in a matrix

Question

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));
    }

Answer 1

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).

Following are couple of solutions:

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);
   }
   

2. 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)
   }
   

Assumptions:

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)
   

and sum it up. i.e., the sum would be

 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) 

in the DP solution.

2. The destination cell is reachable from source cell and both the source and destination cells are enclosed in the original matrix (based on dimensions of the matrix)