Robot And Paths Problem Using Dynamic Programming in C++

Robot And Paths Problem Using Dynamic Programming Png

Today, we’ll learn to solve robot and paths problem using dynamic programming in C++. It’s a popular dynamic programming problem on CodeChef. Dynamic programming is a great way to solve problems that revolve around paths. So without wasting time, let’s get started.

Problem Statement for Robot And Paths Problem

Given a grid of size (M x N). A robot enters the grid from the coordinates (0, 0). Some cells of the grid are blocked. Find out the total number of ways the robot can take to reach the cell (M – 1, N – 1). Note: the motion of the robot is limited to one step towards the South or one step towards the east.

Input Format

The first line of the input will be the dimensions of the grid i.e. R, C and the number of cells blocked in the grid. The following P lines will contain the coordinates of the blocks.

For example,

Input:
4 3 2
3 3
3 1

Solution:
2

Approach

How To Deal With Dynamic Programming Problems

In dynamic programming, we never waste our previous computations. This distinguishes dynamic programming from recursion. We use dynamic programming because it makes the solution many times more optimum than recursive solutions.

Pseudocode

Below is the step-by-step process that we’ll follow to code the solution.

  • To reach the cell (i, j), we can only come through two paths.
    • Through (i – 1, j)
      • By descending one level from the upper row.
    • Or through (i, j – 1)
      • By moving one step towards the east.
  • Create a 2D array to store the answers to smaller subproblems.
  • The total number of ways for each cell is the result of the recursive relation.
    • Recusive relation: dp[i][j] = dp[i – 1][j] + dp[i][j – 1];
  • We’ll check for the base cases first.
    • if(i == 0 || j == 0)
    • It represents either the topmost row or the leftmost column.
    • There’s only a single way to reach the elements in these rows, given that there’s no block.
  • If top cell is blocked : dp[i][j] = dp[i][j – 1]
  • If left cell is blocked : dp[i][j] = dp[i – 1][j]
  • We’ll do this for all the cells. And store the answers in a dynamic programming array.

Robot And Paths Problem Using Dynamic Programming In C++ Program

#include 
#include 

using namespace std;

#define MOD 1000000007

int dp[1001][1001];

int numberOfWays(int row,int col)
{
	//we are assuming the indexing to start from (0,0) and current postion to be (0,0)
	//base cases
	if(dp[0][0] == -1)
	{
		//if the first cell is blocked it means that we cannot go anywhere 
		cout<<"Entrance is blocked"<>M>>N>>P;

	cout << "Enter the locations of blocks" << endl;
	for(int i=0;i>x>>y;

		//mark all the blocked cells 

		dp[x-1][y-1]=-1;	
	}

	cout<<"Initially the DP array is :"<
Image 29
Image 30

Output

Image 31

Conclusion

Today, we solved the robots and paths problem dynamic programming in C++. We used the concept of recursion + memoisation(Dynamic Programming) to solve this problem. We used the bottom-up approach to develop this solution. In the end, we implemented a C++ program to demonstrate the working of our solution. That’s all for today, thanks for reading.