Question

A computer programmer lives in his home located at the upper left corner of the following street grid and works in a building located at the right lower corner. In the grid, lines represent streets. There are five horizontal streets and seven vertical streets. On his way to work, he can drive along any street and turn at any intersection, but can only go down or right, and cannot go back. How many different paths are there for him to drive from home to work? Describe your algorithm, define all variables, write down the recurrent formulas and boundary conditions to solve this problem, and show your calculation to find the total number of paths for this question. A correct number with no formula and calculation may receive a zero score.

(The grid wouldnt post but it is a simple 4 X 6 grid)

Answer 1

Here is the solution for the following problem. Since you did not mention the language, I am providing you solution in C++.

If you want the solution in another language please feel free to ask.

There are five horizontal streets and seven vertical streets.

It means we have a matrix of : 5 x 7 grid

---------------------------------------------------------------------------------------------------------------------------------------------

Constraint: Can only move right or in down direction

----------------------------------------------------------------------------------------------------------------------------------

Variable used : rows  //store the number of rows

cols // store the column in grid

totalPaths //store total number of paths

-----------------------------------------------------------------------------------------------------------------------------------------

Boundry Condition:

Start from the destination and if reaches at the source , count it as a path

At source the row = 1 and col = 1

// If either given row number is first or given column number is first
if (m == 1 || n == 1)
return 1;

-------------------------------------------------------------------------------------------------------------------------------------

Code:

#include<iostream>
using namespace std;

int numberOfPaths(int m, int n)
{
// If either given row number is first or given column number is first
if (m == 1 || n == 1)
return 1;

return numberOfPaths(m - 1, n) + numberOfPaths(m, n - 1);
// + numberOfPaths(m-1, n-1);
}
  
int main()
{
int rows = 5;
int cols = 7;
int totalPaths = 0;
totalPaths = numberOfPaths(rows, cols);
cout << "Number of Paths: " << totalPaths;
return 0;
}

-----------------------------------------------------------------------------------------------------------------------------------

Output:

Number of Paths: 210