Robot Paths Problem Using Dynamic Programming in C++

Counting routes from the top-left to the bottom-right means accounting for cells the robot cannot enter. Dynamic programming counts routes to each open cell by adding the counts from above and from the left.

In this piece, I’ll show how to map blocked coordinates to C++ indices and use one row of DP values to count routes.

TL;DR

Count valid routes by adding the counts of reachable predecessor cells.

• The start has one path when it is open. Every other cell starts with zero.
• Convert the input’s one-based blocked coordinates to zero-based row and column indices.
• A single row of DP values is enough. The program takes O(R*C) time and stores O(C) path counts alongside the blocked-cell grid.
• The target CodeChef variant uses modulo 1,000,000,007. Follow the statement for a different platform’s variant.

What Is the Robot and Paths Problem?

In this grid problem, the robot moves one cell at a time from top-left to bottom-right using only right and down moves, while input coordinates mark blocked cells.

With right and down as the only moves, the last step into a cell comes from above or the left, so the predecessor groups do not overlap. Their counts can be added once each, while an obstacle has zero routes and the destination value is a total rather than a shortest distance.

Define ways[r] as the number of valid partial routes ending at row r, column c. The table gives the base, obstacle, and boundary values.

For four rows and three columns with blocked input coordinates (3, 3) and (3, 1), the path counts after each row are:

On row one, every open cell inherits one route, giving (1, 1, 1). In row two, the middle cell receives one route from each side, and the third adds those two to the one above, giving (1, 2, 3). The two obstacles in row three clear columns one and three, leaving (0, 2, 0).

On the final row, column two keeps two routes and passes them to the destination because the cell above it is blocked. The surviving moves are right, down, down, down, right and down, right, down, down, right, so both routes enter from row four, column two. The answer is 2.

How to Solve Robot and Paths in C++ Step by Step

The program marks all blocked cells before it begins counting routes.

Step 1: Map the input to grid cells

The input begins with R rows, C columns, and P blocked coordinates. Each coordinate in this version is one-based, while a C++ vector begins at index zero, so subtract one from both values when marking a cell.

A square grid can hide a transposed coordinate pair because the swapped cell may remain in bounds. A non-square test often exposes a swap through the bounds check. With four rows and three columns, swapping valid (4, 3) to (3, 4) makes the column exceed its limit.

Step 2: Add the two predecessor counts

The open start is the base case for the loop.

• The loop checks the obstacle flag first and explicitly sets a blocked slot to zero.
• At row zero, read only from the left. In the first column, use zero for the missing left value and keep the value from above, which avoids an invalid index.

Step 3: Keep one row of path counts

As the scan reuses one row, its slots play two roles during an update. The table shows which row each value represents.

A reverse scan would read the stale previous-row value in dp[col – 1] and miss routes from the current row’s left. Reading P pairs and visiting each cell costs O(P + R*C) time, with O(R*C) obstacle flags and O(C) DP values.

A sparse set can reduce obstacle storage to expected O(P) when P is small, but hashing adds work for each cell check.

A full table preserves all intermediate counts for debugging. Memoized recursion can skip unreachable cells but adds cache and call-stack overhead.

Step 4: Compile and run the C++ solution

The old snapshot used a fixed 1001-by-1001 array, so this version sizes vectors from R and C instead of guessing a cap absent from the readable statement.

#include <iostream>
#include <vector>

using namespace std;

constexpr long long MOD = 1000000007LL;

int main() {
    int rows, cols, blockedCount;
    if (!(cin >> rows >> cols >> blockedCount)) {
        return 1;
    }
    if (rows <= 0 || cols <= 0 || blockedCount < 0) {
        return 1;
    }

    vector<vector<char>> blocked(rows, vector<char>(cols, false));
    for (int k = 0; k < blockedCount; ++k) {
        int inputRow, inputCol;
        if (!(cin >> inputRow >> inputCol)) {
            return 1;
        }
        if (inputRow < 1 || inputRow > rows || inputCol < 1 || inputCol > cols) {
            return 1;
        }
        blocked[inputRow - 1][inputCol - 1] = true;
    }

    vector<long long> dp(cols, 0);
    for (int row = 0; row < rows; ++row) {
        for (int col = 0; col < cols; ++col) {
            if (blocked[row][col]) {
                dp[col] = 0;
            } else if (row == 0 && col == 0) {
                dp[col] = 1;
            } else {
                const long long fromLeft = (col > 0) ? dp[col - 1] : 0;
                dp[col] = (dp[col] + fromLeft) % MOD;
            }
        }
    }

    cout << dp[cols - 1] << '\n';
    return 0;
}

Save that source as robot_paths.cpp and save the sample input beside it as sample.in. The first line gives four rows, three columns, and two blocked cells. The following lines block the third cell in row three and the first cell in row three.

4 3 2
3 3
3 1

Compile and run the named source file with this command:

g++ -std=c++17 -O2 -Wall -Wextra -pedantic robot_paths.cpp -o robot_paths && ./robot_paths < sample.in

Running the sample command prints this result:

2

I ran the sample with the command above. It printed 2 and exited with code 0. I tested blocked-start and blocked-destination cases, and both returned 0.

The output matches the hand-checked DP rows above. The first and last cells are open, and the two blocked positions do not cut off both possible routes to the destination.

Edge Cases in the Robot Paths DP

Boundary cells are worth checking because a wrong update order or stale slot first shows up at the grid’s edges.

Because the obstacle grid stores boolean flags, reading the same coordinate twice writes true again and leaves the same cell blocked. P still counts input pairs, not unique blocked cells.

Use this checklist when a count looks wrong:

• With no blocked coordinates, confirm that the top row and left column each continue with one route.
• Place a blocked cell in each boundary and trace whether its neighboring counts stop at that point.
• Block both predecessors of one cell and confirm that its count becomes zero.
• On a tiny grid, compare DP with a recursive right/down counter. This check can catch indexing errors, but overlapping subproblems make recursion too slow for large inputs.

Allowing up or left can break this row-major order and introduce cycles, so the one-pass recurrence may no longer apply. For unit-cost moves in four directions, breadth-first search is a common starting point for shortest paths.

Follow the input contract for each variant

Before reusing code, compare how the statement encodes blocked cells and limits the answer.

On an unobstructed R-by-C grid, choose(R+C-2, R-1) gives the number of routes, but blocked cells require the obstacle-aware recurrence. For an open 3-by-4 grid, five moves include two downward steps, so choose(5, 2) gives 10 routes. This is a quick check when P is zero, while obstacles make the simple formula inapplicable by itself.

This variant requires modulus 1,000,000,007, though other unique-path tasks may ask for an exact count. Each stored operand is below MOD, so their sum is below 2,000,000,014 and fits in long long. Reducing after each cell preserves the final modular result and keeps stored counts below MOD.

Before allocating or indexing, the program rejects missing dimensions, nonpositive grid sizes, negative P, truncated coordinate pairs, and any pair outside rows 1 through R or columns 1 through C. Valid contest input should pass these checks, while malformed input returns before it can cause an out-of-range vector access.

Conclusion

The compiled example and edge-case table give you a concrete check when you adapt this approach to a different input format.

To practice another recurrence-based C++ example, read the Friends Pairing Problem in C++. For a problem where each state compares choices, continue with Optimal Game Strategy in C++.

FAQ

These quick answers cover input, obstacle, storage, and modulus choices that vary by problem statement.