Find Path through grid – constrained motion

Introduction

This is another addition to the backtracking series of problems. The problem is asked in many interviews in many different forms. Here are few of them:

  • Given a grid where few of the cells are blocked. You have a robot placed at the top left corner of the grid. Find path through grid such that the robot starts from the top left corner and moves to the bottom right corner.
  • Another form just asks for all possible paths from one cell to another into a grid.

Of course there are constraints on the movement of the robot, else you would end up going in circles and the paths wont be correct and short. Here are few types of constraints

  • The robot can only move one step at a time
  • It can only take a step to the right or to the bottom relative to its current position
  • The robot cannot step on a blocked cell
  • In few scenarios, it can also move to the south west cell relative to its current position

Limiting the problem

For the purpose of this post, we will only consider the first three constraints in motion. Hence, we need to design an algorithm where in a M*N grid, the robot is placed at (0,0) and can move to the right or down direction one step at a time and has to reach the cell (M-1, N-1)

As we all are aware that there can be many paths which can satisfy the constraints and hence serve as the solution to this problem. However, in this post we will focus on printing any one path from the numerous possibilities. I will write a separate post for printing all the paths.

Here is a pictorial representation of the problem definition.

robotinagrid

Approach

The argument for the approach is similar to other backtracking solutions. First we need to define what a safe/valid move is.

Defining Safe Move

  • The target cell must be within the boundaries of the board.
  • It must not be blocked.

Here is the source code for the isSafe function:

Defining the Strategy

Let the robot be at coordinates (r,c). There are only two possibilities based on the MOVES array. Either it can move to (r+1, c) or (r, c+1). The next cell is chosen based on the outcome of isSafe method. And then it recursively moves from the next cell to the destination.

There are two possibilities,

  • Either the current chosen path ends up at the destination or
  • It is blocked or not safe.

In case it is blocked or unsafe, the robot tries the next value in the MOVES array.

  • If trying another value from the array, lands it at the destination, the method returns true and it is propagated up the recursion stack and finally it returns to the caller.
  • If trying another value, does not lead to destination, then a false is returned up the stack and at any level in the stack , if there are moves still remaining, they are tried and the process is repeated until all moves are tried.

Hence, the code will always produce either a valid path or an indication that the robot cannot reach the destination in given circumstances. Let me put down some code so that its easy to understand.

Source Code

Additional Code

This is how, the method should be invoked.

Analysis

Let us evaluate the length of one path. As there are N rows and M columns. So the path from source to destination would have M + N cells. In each step of the recursion, the robot travels just one cell. So the depth of the recursion would be M+N.

The only auxiliary space is used for the recursion stack and as the depth of the recursion tree is M+N, the stack will require space proportional to M+N. So we can write the space complexity as O(M+N)

For the running time, we will write the recurrence equation:

T(M+N)  = 2 * T(M+N – 1) + O(1) . This means that the recursion tree branches into two at each level and the problem size reduces by 1. Total number of nodes in the tree would be 2^(M+N). Hence we can write T(N) = O(2^M+N).

Here is a representation of the recursion tree for a grid of size 3*3. Where the robot starts at (0,0) and stops at (2,2)

Find Path through grid

The above is a more generic recursion tree which shows how the recursion will reduce the problem by 1 at each level. At each level, there are two paths left or down, hence the branching factor of 2. Eventually the path length is 6 hence there are 5 levels in the tree.

Find Path through grid

The above is another version of the same recursion tree, a precise one. The root signifies that we start at (0,0). Then there are two possible paths, (0,1) and (1,0), hence two branches. Then each branch further branches into two possible directions. So, by the time we reach the leaves, the robot is at the destination. Check the leaf nodes, which is (2,2) for each path.

Summary

Please comment below if you need help with the recursion tree or any other point which was unclear. I will try to elaborate on the same. In the next post, we will learn about printing all the possible paths.