DEV Community

loading...
Nlogn

Find if a path is possible in a NxM for reaching bottom right form top left

mayankjoshi profile image mayank joshi Originally published at nlogn.in Updated on ・2 min read

A robot sitting on the upper left corner(0,0) of a grid with r rows and c columns.
The robot can only move in two directions: right or down, but certain cells are “off-limits” such that the robot cannot step on them. Design an algorithm to find if there exists a path for the robot for reaching the bottom right from the top left.

The problem requires an understanding of Dynamic Programming. Read here…


The first grid has many possible paths of reaching destination(e) form source(s) and one of them is shown using green. In the second grid, there is no possible path to reach the destination from the source.

Algorithm

  1. Let’s start from the end(r,c) and start walking in up(r-1,c) and left(r,c-1) direction.
  2. If we encounter an off-limit, we will take the alternate path.
  3. If both the path contains the off-limit, stop returning no possible path.
  4. Repeat the above steps until we reach the source and return true(path is possible).

Since the subproblems involve repetition, Dynamic Programming is used to speed up and reduce time complexity.

Implementation of above algorithm in CPP

In the above program, the dp[i][j] is used to store the values of subproblems. It is assigned -1, which tells that the current step/subproblem is not computed and -2, tells that it is invalid of the off-limit grid.

Output

true

TIME COMPLEXITY

The time complexity of the above program is O(RC), where R is the number of Rows(r) and C is the number of Columns(c) using Dynamic Programming.


Follow us to stay updated with interview and competitive programming related questions. 👨‍💻 👨‍💻

Discussion (0)

pic
Editor guide