# Count the number of paths from point A to B

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

- Start from row-0, column-0.
- 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.
- if x < m and y < m then go to Step 3 else return to the previous recursive call.
- 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.)
- 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; }