Question

Java Programming Question

The problem is to count all the possible paths from top left to bottom right of a MxN matrix with the constraints that from each cell you can either move to right or down.Input:
The first line of input contains an integer T, denoting the number of test cases. The first line of each test case is M and N, M is number of rows and N is number of columns.Output:
For each test case, print the number of paths.Constraints:
1 ≤ T ≤ 30
1 ≤ M,N ≤ 10Example:
Input
2
3 3
2 8Output
6
8Explanation:
Testcase 1: Let the given input 3*3 matrix is filled as such:
A B C
D E F
G H I
The possible paths which exists to reach 'I' from 'A' following above conditions are as follows:
ABCFI, ABEHI, ADGHI, ADEFI, ADEHI, ABEFI.

Answer 1

// Defines a class AllPossiblePath to display all possible path

// in a matrix

public class AllPossiblePath

{

/*

* Recursive method to print all possible path

* matrix: Contains data for the matrix of size row x col

* row and col: Represents row and column dimension of the matrix

* r and c: Represents the current index position of row and column

* currentPath: To store the current path

*/

private static void printAllMatrixPath(int matrix[][], int row, int col,

int r, int c, int currentPath[], int index)

{

// Stores the matrix current r and c index position value

// at index position of currentPath array

currentPath[index] = matrix[r][c];

  

// In order to move right checks if current row index is less then the

// maximum number of rows minus one

if (r == row - 1)  

{

// Reached bottom of the matrix so, left with

// only option to move right

for (int k = c + 1; k < col; k++)

currentPath[index + k - c] = matrix[r][k];

  

for (int l = 0; l < index + col - c; l++)

System.out.print(currentPath[l] + " ");

System.out.println();

return;

}// End of if condition

  

  

// In order to move downward checks if current column index is less then the

// maximum number of columns minus one

if (c == col - 1)  

{

// Reached the right corner of the matrix so, left with

// only the downward movement.

for (int k = r + 1; k < row; k++)  

currentPath[index + k - r] = matrix[k][c];

  

for (int l = 0; l < index + row - r; l++)

System.out.print(currentPath[l] + " ");

System.out.println();

return;

}// End of if condition  

  

// Recursively call the method to display all the paths

// possible after moving down

printAllMatrixPath(matrix, row, col, r + 1, c, currentPath, index + 1);

  

// Recursively call the method to display all the paths

// possible after moving right

printAllMatrixPath(matrix, row, col, r, c + 1, currentPath, index + 1);

}// End of method

  

// main method definition

public static void main(String[] args)  

{

// Number of rows and columns

int row = 3;

int col = 3;

// Creates a matrix

int matrix[][] = { { 1, 2, 3 },  

{ 4, 5, 6 },

{ 7, 8, 9 }

};

// Calculates the maximum path length

int maxPathLength = row + col - 1;

// Calls the method to print all possible path in matrix

printAllMatrixPath(matrix, row, col, 0, 0, new int[maxPathLength], 0);

}// End of main method

}// End of class

Sample Output:
1 4 7 8 9
1 4 5 8 9
1 4 5 6 9
1 2 5 8 9
1 2 5 6 9
1 2 3 6 9