In this article, we will be seeing how to calculate the number of paths along a grid. The previous article focused on calculating the number of squares and rectangles in an m*n grid.

While simple grids can be easily solved using the permutations with repetition approach, few of the variations can trouble even the best of aspirants. Let’s take a look at the concepts and possible ways of getting around tricky problems.

Simple grids

These are easy to solve and straightforward grids with no obstacles or shortcuts. One has to simply move from point A to point B taking the shortest possible route and the number of such routes have to be calculated. Take for example this grid:

The question asks us to find all the possible shortest routes from A to B. Now, shortest route essentially means that a person has to keep on moving towards the right and the top and so, taking a left or coming down one step is not allowed. So, one has to take 5 right steps and 4 up steps to reach B from A and the order is not important. This means that you have to re-arrange the letters RRRRRUUUU in all possible ways. This can be done in:

So, for any m*n grid, the number of ways in which you can go from one point to a diagonally opposite point is given by:

Shortcuts

In this type, we have a shortcut going through the grid. Let’s take the following example:

We have a path C which shortens the route by a bit. Now, it is important to note that if there has to be a shortest path between A and B, it has to pass through C. So, you have to reach path C for sure and then, go to the other end and then start towards B again. Let’s name the points and then trace the paths:

So, we have to reach from A to D, then D to E and finally from E to B. A to D is a normal 2*2 grid which can be covered in 4!/(2!2!) = 6 ways. D to E is a single path and E to B can be covered in 3!/(2!1!) = 3 ways. So, a total of 6*3=18 ways.

Remember that we have used ‘and’ and so, we will multiply the individual paths that we get.

Obstacles

In case of obstacles, there will be certain paths that will be blocked and so, cannot be used. So, in these cases, you are supposed to find the total number of valid paths along the grid. Let’s see an example:

We can see that a certain portion of the grid is covered and so, we cannot traverse that path. So, how do we solve these questions? These are probably the trickiest of grid based questions and if you can understand the construction of paths, you should be good to go.

We can see that because of the obstruction, we would be forced to pass through either C1 or C2 or C3 or C4. There is no other way in which we can walk through the grid. In other words, these routes are mutually exclusive and cumulatively exhaustive. So, we will calculate for each of the individual routes and then find the total number of routes.

A-C1: 5 ways, C1-B: 1 way. Total 5 ways.

A-C2: 10 ways, C2-B: 4 ways. Total 40 ways.

A-C3: 5 ways, C3-B: 4 ways. Total 20 ways.

A-C4: 1 way, C4-B: 1 way. Total 1 way.

So, 66 routes in total.

Using these methods, you can easily solve any grid based problem involving either shortcuts or obstacles. You have to convert the grid into simple m*n grids and then club the number of ways together to get to the answer.