CC-11 : Find number of paths from top left element of matrix to bottom right element.

Description:

Given an input matrix, find number of paths from the top-left element of matrix to bottom-right element of matrix.

Test cases and expected outputs:

Input Parameters	Expected outputs
3x3 matrix	Paths from first node to last node in 3x3 matrix : 6

Pseudocode:

getMatrixStartToEndPaths(startX, startY, endX, endY):

The co-ordinates of top-left and bottom-right elements are received as input parameters .

If startX==endX or startY==endY, return 1; (base case).

Set int variable downPaths as return value from recursive call to getMatrixStartToEndPaths(startX+1, startY, endX, endY).

Set int variable rightPaths as return value from recursive call to getMatrixStartToEndPaths(startX, startY+1, endX, endY)

Return downPaths + rightPaths.

Code:

public int getMatrixStartToEndPaths(int startX,int startY, int endX, int endY){
	if ((startX==endX)||(startY==endY)){return 1;}
	int downPaths=getMatrixStartToEndPaths(startX+1, startY, endX, endY);
	int rightPaths=getMatrixStartToEndPaths(startX, startY+1, endX, endY);
	return downPaths+rightPaths;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class RecursionGetMatrixStartToEndPaths {

public int getMatrixStartToEndPaths(int startX,int startY, int endX, int endY){
	if ((startX==endX)||(startY==endY)){return 1;}
	int downPaths=getMatrixStartToEndPaths(startX+1, startY, endX, endY);
	int rightPaths=getMatrixStartToEndPaths(startX, startY+1, endX, endY);
	return downPaths+rightPaths;
}

public static void main(String[] args) {
	/************************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	RecursionGetMatrixStartToEndPaths rcn=new RecursionGetMatrixStartToEndPaths();
	int matSizeX=3;
	int matSizeY=3;
	retVal=rcn.getMatrixStartToEndPaths(0,0,matSizeX-1,matSizeY-1);
	System.out.print("Paths from first node to last node in 3x3 matrix : "+ retVal);	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
}
		
}


}