The problem is to count all the possible paths from top left to the bottom right of an MxN matrix with the constraints that from each cell you can either move to the 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 the number of rows and N is the number of columns.

Output:

For each test case, print the number of paths.

In this problem our task is to count the number of paths through which we can go from row — 0, column — 0 to row — n-1, column — n-1.

We will be using recursion to solve the given problem.

This question has been previously asked in Amazon, Microsoft, and Zoho.

A simple recap — Recursion is a technique of iteration in which a function calls itself.

The approach to solve the problem is, that we will start moving from (0,0) and take one step at a time by either moving towards right or bottom.

If suppose we reach a point where x == m-1 and y == n-1, we have reached our destination and we simply return back.

Let’s try writing an algorithm for the given problem.

Let m = no. of rows, n = no. of columns

  1. Start from row-0, column-0.
  2. if x == m-1 and y == n-1, this means we have reached our destination. In this case, increment c by 1, where c is counter for the number of paths.
  3. if x < m and y < m then go to Step 3 else return to the previous recursive call.
  4. Move one column towards the right (y = y+1) and go to Step 2. (This step is a recursive call as given in the code below.)
  5. Move one column towards left (x = x+1) and go to Step 2. (This step is a recursive call as given in the code below.)

Below given code for the above problem is in the C++ programming language.

#include<iostream> 
using namespace std; 
void numPaths(int x, int y, int m, int n, int *c)
{ 
if(x == m-1 && y == n-1){
 *c = *c + 1; 
 return; 
} 
if(x < m && y < n){
 numPaths(x,y+1,m,n,c);
 numPaths(x+1,y,m,n,c); 
} 
} 
int main(){
 int t,m,n,c;
 cin >> t;
 for(int a = 0 ; a < t ; a++){
 c=0;
 cin >> m;
 cin >> n;
 numPaths(0,0,m,n,&c);
 cout << c << "\n";
 } 
return 0; 
}