Unique paths with obstacles and the binomial shortcut

Why this matters

Many programs move something across a grid of squares. A robot in a warehouse, a character on a tile map and a delivery van on a street plan all move this way. A common question is how many different routes exist from the start to the finish.

Answering it teaches a two-dimensional table. The tabulation lesson in this module built a table with one dimension, a single row. This lesson uses a table with rows and columns.

The lesson does two things. First it counts routes when some squares are blocked, using a table. Then it counts routes on an empty grid with a formula called the binomial coefficient, which needs no table at all. The formula is much faster, but it only works when nothing is blocked. You will see why.

The problem in plain words

A grid is a rectangle of squares, like graph paper. Each square is a cell. The horizontal lines of cells are rows, and the vertical lines are columns. This lesson numbers rows and columns from 0, starting at the top left. The cell in row 2, column 5 is written as (2, 5).

Each cell is either free or blocked. A blocked cell is an obstacle. You start at the top-left cell, (0, 0), and want to reach the bottom-right cell. Each move takes one step right or one step down. You may not step onto a blocked cell, and you may not leave the grid.

A route is one full sequence of moves from start to finish. Two routes are different when they differ in at least one move.

Take a 3 by 3 grid with no obstacles. It has 3 rows and 3 columns. Every route from the top left to the bottom right takes 2 steps down and 2 steps right, in some order. Write R for right and D for down. The six routes are:

RRDD
RDRD
RDDR
DRRD
DRDR
DDRR

Now block the centre cell, (1, 1). Four of the six routes pass through it: RDRD, RDDR, DRRD and DRDR. Only RRDD and DDRR avoid it. So the answer for this grid is 2.

Every section below uses this question: how many routes exist, given which cells are blocked.

The idea: count the routes into each cell

Pick any free cell and ask how many routes reach it from the start. Look at the last move that brought you there. That move was either a step down from the cell above, or a step right from the cell to the left.

These two groups of routes do not overlap, because the last move is different in each group. So the count for the cell is the count for the cell above, plus the count for the cell to the left.

Two edge cases follow from this rule:

A cell in the top row has no cell above it. Treat the missing cell as 0.
A cell in the left column has no cell to its left. Treat the missing cell as 0.

The start cell has no neighbours before it. It gets the value 1, because there is exactly one way to be at the start: do nothing.

A blocked cell gets 0, because no route can stand on it.

Now follow the recipe from the tabulation lesson.

Define ways[r][c] in one plain sentence: the number of routes from the start to cell (r, c). A blocked cell holds 0.
Base case: ways[0][0] is 1 when the start is free, and 0 when it is blocked.
Recurrence: for a free cell, ways[r][c] equals ways[r - 1][c] plus ways[r][c - 1], where a neighbour that does not exist counts as 0.
Loop order: go row by row, and left to right inside each row. Then the cell above and the cell to the left are always filled before they are read.
Answer: the value in the bottom-right cell, ways[rows - 1][cols - 1].

Worked example 1: the 3 by 3 grid with a blocked centre

Start with the centre blocked. Fill the table one row at a time, using the rule from the last section.

row 0:   1  1  1
row 1:   1  0  1
row 2:   1  1  2

Check each row by hand.

Row 0 has no row above it, so each cell takes only the cell to its left. The start is 1, and the two cells to its right each take 1 from the left.

Row 1 starts with (1, 0). Nothing is to its left, and the cell above is 1, so the value is 1. The centre (1, 1) is blocked, so it is 0. The cell (1, 2) takes 1 from above and 0 from the left, so it is 1.

Row 2 starts with (2, 0). The cell above is 1, so the value is 1. The cell (2, 1) takes 0 from above, because the centre is blocked, and 1 from the left, so it is 1. The cell (2, 2) takes 1 from above and 1 from the left, so it is 2.

The answer is 2, which matches the list of routes.

Now the same grid with no obstacle:

row 0:   1  1  1
row 1:   1  2  3
row 2:   1  3  6

The bottom-right cell is 6, which matches the six routes listed earlier. Each cell in the middle is the sum of the cell above and the cell to its left. The blocked centre is the only thing that changed the table.

The first program

The program below builds the whole table for a grid, then reads the answer from the last cell. The grid uses 1 for blocked and 0 for free, so grid[r][c] == 1 means the cell is blocked.

The program prints the answers for four grids, the one-row version on two of them, and the table for a 4 by 4 grid with a diagonal of obstacles.

C++ · editable

#include <iostream>
#include <vector>

// grid[r][c] is 1 when the cell is blocked and 0 when it is free.
// ways[r][c] is the number of walks from the top-left cell to (r, c).
std::vector<std::vector<long long>> fill_table(const std::vector<std::vector<int>>& grid) {
    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
    std::vector<std::vector<long long>> ways(rows, std::vector<long long>(cols, 0));

for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (grid[r][c] == 1) {
                ways[r][c] = 0;
            } else if (r == 0 && c == 0) {
                ways[r][c] = 1;
            } else {
                long long from_above = (r > 0) ? ways[r - 1][c] : 0;
                long long from_left = (c > 0) ? ways[r][c - 1] : 0;
                ways[r][c] = from_above + from_left;
            }
        }
    }
    return ways;
}

long long count_paths_2d(const std::vector<std::vector<int>>& grid) {
    return fill_table(grid).back().back();
}

// The same count, keeping only one row of the table at a time.
long long count_paths_1d(const std::vector<std::vector<int>>& grid) {
    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
    std::vector<long long> row(cols, 0);

for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (grid[r][c] == 1) {
                row[c] = 0;
            } else if (r == 0 && c == 0) {
                row[c] = 1;
            } else {
                row[c] = row[c] + (c > 0 ? row[c - 1] : 0);
            }
        }
    }
    return row[cols - 1];
}

int main() {
    std::vector<std::vector<int>> open3x3 = {
        {0, 0, 0},
        {0, 0, 0},
        {0, 0, 0},
    };
    std::vector<std::vector<int>> open3x7(3, std::vector<int>(7, 0));
    std::vector<std::vector<int>> middle_blocked = {
        {0, 0, 0},
        {0, 1, 0},
        {0, 0, 0},
    };
    std::vector<std::vector<int>> start_blocked = {
        {1, 0},
        {0, 0},
    };
    std::vector<std::vector<int>> wall = {
        {0, 0, 0, 0},
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 0},
    };

std::cout << "3x3 open:            " << count_paths_2d(open3x3) << "\n";
    std::cout << "3x7 open:            " << count_paths_2d(open3x7) << "\n";
    std::cout << "3x3, centre blocked: " << count_paths_2d(middle_blocked) << "\n";
    std::cout << "start blocked:       " << count_paths_2d(start_blocked) << "\n";
    std::cout << "1D 3x3, centre blocked: " << count_paths_1d(middle_blocked) << "\n";
    std::cout << "1D 3x7 open:            " << count_paths_1d(open3x7) << "\n";

std::cout << "\nTable for the 4x4 wall:\n";
    for (const auto& row : fill_table(wall)) {
        for (long long value : row) {
            std::cout << value << " ";
        }
        std::cout << "\n";
    }
    std::cout << "4x4 wall answer: " << count_paths_2d(wall) << "\n";
    return 0;
}

Output:

3x3 open:            6
3x7 open:            28
3x3, centre blocked: 2
start blocked:       0
1D 3x3, centre blocked: 2
1D 3x7 open:            28
 
Table for the 4x4 wall:
1 1 1 1 
1 0 1 2 
1 1 0 2 
1 2 2 4 
4x4 wall answer: 4

Some points in the code are worth slowing down for.

fill_table returns the whole table, not just the answer. The caller can then print any cell. count_paths_2d reads the bottom-right cell with back().back(). back() gives the last row, and the second back() gives the last cell in that row.

The blocked check comes first. A blocked start therefore stores 0, even though the start is normally the cell that gets 1. That is why the output for the blocked start is 0.

The static_cast<int> calls turn the vector sizes into plain int values. Vector sizes have an unsigned type, and mixing unsigned and signed numbers in arithmetic causes subtle bugs. Converting once at the top keeps the rest of the code simple.

The wall table shows that a blocked cell removes only the routes through it. The cell (2, 3) is 2. Its cell above, (1, 3), holds 2, and its cell to the left, (2, 2), is blocked, so it adds 0.

Worked example 2: keeping one row at a time

The row for r depends only on the row above it and on earlier cells in the same row. So a single array with one entry per column can serve as the whole table. This is the one-dimensional version in the program, count_paths_1d.

The trick is in the order of updates. Before the loop reaches column c in row r, row[c] still holds the value from the row above. That is the value the rule calls ways[r - 1][c]. The entry row[c - 1] has already been updated for this row, so it holds ways[r][c - 1]. The line

row[c] = row[c] + (c > 0 ? row[c - 1] : 0);

is therefore the same recurrence as before, written with one array.

The loop must go left to right. If it went right to left, row[c - 1] would still hold the old value from the row above, and the sum would be wrong.

The 1D version gives the same answers as the 2D version on both grids in the output.

The binomial shortcut for an open grid

Now remove every obstacle. Count the moves first. A route from the top left to the bottom right must take rows - 1 steps down and cols - 1 steps right. Call the total number of steps t, so t = rows + cols - 2.

On an empty grid, every order of those steps is a valid route, because nothing stops any step. A route is therefore fully described by choosing which of the t steps are down steps. The choice is rows - 1 items picked from t.

That count has a name. The binomial coefficient C(n, k), read "n choose k", is the number of ways to pick k items from n items when the order of the picks does not matter.

A small example makes this concrete. Label four items a, b, c and d. The ways to pick two of them are ab, ac, ad, bc, bd and cd. That is six ways, so C(4, 2) = 6.

Apply this to the 3 by 3 grid. It has t = 3 + 3 - 2 = 4 steps, and 2 of them are down steps. So the count is C(4, 2) = 6, which matches the list of routes.

The general rule for an open grid is:

routes = C(rows + cols - 2, rows - 1)

Check it on a second grid. A 3 by 7 grid has t = 3 + 7 - 2 = 8 steps, and 2 of them are down steps. So the count is C(8, 2) = 28. The table from the first program gives 28 for the same grid, so the two methods agree.

The formula behind C(n, k) is n! / (k! * (n - k)!), where n! means n * (n - 1) * ... * 1. That form is hard to compute safely for large numbers, because the factorials grow very fast. The next section uses a safer way to compute the same value.

Computing the binomial without overflow

A computer stores whole numbers in a fixed number of bits. An unsigned long long holds values from 0 up to 18,446,744,073,709,551,615. A result above that limit does not raise an error. It wraps around and becomes a smaller, wrong number. This problem is called overflow.

The first version below multiplies and divides step by step:

result = result * (n - k + i) / i;

This version can overflow even when the final answer fits. The multiplication happens before the division, so the intermediate product can be far larger than the answer.

The second version builds Pascal's triangle, where each number is the sum of the two above it, one row at a time, using only additions. The rule C(a, b) = C(a - 1, b - 1) + C(a - 1, b) lets a single row hold the values for every b. Each value in this row is at most the final answer, so nothing overflows when the answer itself fits.

Both versions are in the program below. The program also uses k = min(k, n - k). This is valid because C(n, k) equals C(n, n - k). Choosing the smaller side keeps the loop short.

C++ · editable

#include <algorithm>
#include <iostream>
#include <vector>

// Multiplicative formula: each step multiplies before it divides.
unsigned long long binomial_naive(int n, int k) {
    unsigned long long result = 1;
    for (int i = 1; i <= k; ++i) {
        result = result * (n - k + i) / i;
    }
    return result;
}

// Pascal's triangle, one row at a time. Only additions, so no step
// is larger than the final answer.
unsigned long long binomial(int n, int k) {
    if (k > n - k) {
        k = n - k;
    }
    std::vector<unsigned long long> row(k + 1, 0);
    row[0] = 1;
    for (int a = 1; a <= n; ++a) {
        for (int b = std::min(a, k); b >= 1; --b) {
            row[b] += row[b - 1];
        }
    }
    return row[k];
}

// Paths in an open grid with rows x cols cells.
unsigned long long open_grid_paths(int rows, int cols) {
    return binomial(rows + cols - 2, rows - 1);
}

int main() {
    std::cout << "C(5,2) = " << binomial(5, 2) << "\n";
    std::cout << "C(8,2) = " << binomial(8, 2) << "\n";
    std::cout << "C(4,2) naive = " << binomial_naive(4, 2) << "\n";
    std::cout << "open 3x3 = " << open_grid_paths(3, 3) << "\n";
    std::cout << "open 3x7 = " << open_grid_paths(3, 7) << "\n";
    std::cout << "open 33x33 (answer C(64,32)): exact = " << binomial(64, 32)
              << "  naive = " << binomial_naive(64, 32) << "\n";
    std::cout << "open 10x10 = " << open_grid_paths(10, 10) << "\n";
    std::cout << "open 17x17 = " << open_grid_paths(17, 17) << "\n";
    std::cout << "open 34x34 = " << open_grid_paths(34, 34) << "\n";
    return 0;
}

Output:

C(5,2) = 10
C(8,2) = 28
C(4,2) naive = 6
open 3x3 = 6
open 3x7 = 28
open 33x33 (answer C(64,32)): exact = 1832624140942590534  naive = 66050867754679844
open 10x10 = 48620
open 17x17 = 601080390
open 34x34 = 7219428434016265740

The 33 by 33 line shows the problem. The true answer is 1832624140942590534. The naive version prints 66050867754679844 and gives no warning. The last multiplication in the naive loop computes C(63, 31) * 64, which is 58643972510162897088. That number is above the 64-bit limit, so it wraps around.

The Pascal version prints the true answer. It also handles the 34 by 34 grid, whose answer is 7219428434016265740. That value fits in 64 bits. The 35 by 35 grid would need C(68, 34), which is about 2.8 * 10^19. That is above the limit for unsigned long long, so no version in this lesson can return that answer.

The Pascal loop also updates each entry from the highest index down to the lowest. The same reason as in the one-row grid applies. When row[b] is updated, row[b - 1] still holds the value from the previous row.

Why the formula stops working with obstacles

The formula counts every order of the moves. An obstacle removes some of those orders, namely every order that walks into the blocked cell.

You could subtract the routes that pass through each obstacle. But one route can pass through two obstacles, so it would be subtracted twice. Fixing that means adding back some routes, and that leads to longer and longer sums as the number of obstacles grows.

The table handles any pattern of obstacles with the same single rule. That is why the table is the method to use once any cell is blocked. The formula is only the shortcut for the empty grid.

Common mistakes

Forgetting the blocked check. If the code adds the two neighbours even for a blocked cell, the blocked cell still collects routes. The centre-blocked grid then gives the wrong answer. The next program shows this and two other mistakes. It prints the first two results and then fails on the third.

C++ · editable

#include <iostream>
#include <vector>

// Broken on purpose: the blocked cell still receives paths.
long long ignores_blocks(const std::vector<std::vector<int>>& grid) {
    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
    std::vector<std::vector<long long>> ways(rows, std::vector<long long>(cols, 0));
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (r == 0 && c == 0) {
                ways[r][c] = 1;
            } else {
                long long from_above = (r > 0) ? ways[r - 1][c] : 0;
                long long from_left = (c > 0) ? ways[r][c - 1] : 0;
                ways[r][c] = from_above + from_left;
            }
        }
    }
    return ways[rows - 1][cols - 1];
}

// Broken on purpose: no base case for the start cell.
long long no_base_case(const std::vector<std::vector<int>>& grid) {
    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
    std::vector<std::vector<long long>> ways(rows, std::vector<long long>(cols, 0));
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (grid[r][c] == 1) {
                ways[r][c] = 0;
            } else {
                long long from_above = (r > 0) ? ways[r - 1][c] : 0;
                long long from_left = (c > 0) ? ways[r][c - 1] : 0;
                ways[r][c] = from_above + from_left;
            }
        }
    }
    return ways[rows - 1][cols - 1];
}

// Broken on purpose: reads the row above without checking r > 0.
// at() is used so the program reports the bad index instead of
// reading random memory.
long long reads_above_without_check(const std::vector<std::vector<int>>& grid) {
    const int rows = static_cast<int>(grid.size());
    const int cols = static_cast<int>(grid[0].size());
    std::vector<std::vector<long long>> ways(rows, std::vector<long long>(cols, 0));
    ways[0][0] = 1;
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            if (r == 0 && c == 0) continue;
            ways.at(r).at(c) = ways.at(r - 1).at(c) + ((c > 0) ? ways[r][c - 1] : 0);
        }
    }
    return ways[rows - 1][cols - 1];
}

int main() {
    std::vector<std::vector<int>> middle_blocked = {
        {0, 0, 0},
        {0, 1, 0},
        {0, 0, 0},
    };
    std::vector<std::vector<int>> open3x3(3, std::vector<int>(3, 0));
    std::cout << "ignores blocks, centre blocked: " << ignores_blocks(middle_blocked) << std::endl;
    std::cout << "no base case, open 3x3: " << no_base_case(open3x3) << std::endl;
    std::cout << "reads above at row 0, open 3x3:\n";
    std::cout << reads_above_without_check(open3x3) << "\n";
    return 0;
}

Output:

ignores blocks, centre blocked: 6
no base case, open 3x3: 0
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 18446744073709551615) >= this->size() (which is 3)

The first line shows the blocked cell at work. The program counts 6 routes, but only 2 exist. The centre cell received paths and passed them on.

Forgetting the base case. The second line shows the result when the start cell never gets the value 1. Every cell is built from zeros, so the answer is 0 even though the grid is open. The fix is to set ways[0][0] = 1 for a free start.

Reading above the top row. The last two lines are the real error message from at(). The result line in main never prints, because the exception stops the program first. When the row index is r - 1 and r is 0, the value is -1. Converted to an unsigned index, that value is 18446744073709551615, far past the end of the vector. The program stops with std::out_of_range and exit code 134. The check r > 0, as used in the earlier programs, avoids this.

Overflow in the naive binomial. The 33 by 33 line in the binomial output shows no error at all. It only shows a wrong number. When a counting function may return very large values, compare it with a second method on a small grid, or use the Pascal form.

Practice

Exercise 1. A 2 by 2 grid has the top-right cell blocked. How many routes reach the bottom-right cell?

Show the answer

There is only one free route. The two possible routes are RD and DR. RD passes through the blocked top-right cell, so it is out. DR goes down to (1, 0) and then right to (1, 1). The answer is 1.

Exercise 2. A grid has 4 rows and 3 columns, and no obstacles. Use the binomial formula to count the routes.

Show the answer

The route has t = 4 + 3 - 2 = 5 steps. Of those, rows - 1 = 3 are down steps. The count is C(5, 3), which equals C(5, 2) = 10. The table gives the same value, 10.

Exercise 3. Fill in the table for this grid, where 1 is blocked. What is the answer?

0 0 0
1 0 0
0 0 0

Show the answer

The table is:

1 1 1
0 1 2
0 1 3

The cell (1, 0) is blocked, so it holds 0. The cell (1, 1) takes 1 from above and 0 from the left, so it is 1. The cell (2, 2) takes 2 from above and 1 from the left, so it is 3. The answer is 3.

Exercise 4. Explain why the answer is 0 when the start cell is blocked, even though the rest of the grid is free.

Show the answer

Every route begins at the start cell. If the start is blocked, no route can begin. In the table, the only cell that receives the value 1 by the base case is the start, and it is blocked, so it holds 0. Every other cell is built by adding cells above or to the left, and all of those trace back to the start. So every value stays 0.

Exercise 5. Use the binomial formula to count the routes on a 5 by 5 grid with no obstacles. Then check the answer by filling the table.

Show the answer

The route has t = 5 + 5 - 2 = 8 steps, and 4 of them are down steps. The count is C(8, 4) = 70. Filling the table with the same rule gives 70 in the bottom-right cell. The table for this grid has the entries 1, 5, 15, 35 and 70 along its last row.

Summary

Each free cell in a route table holds the count from the cell above plus the count from the cell to its left, and a blocked cell holds 0.
The start cell holds 1, and the answer is the value in the bottom-right cell.
Keeping one row at a time saves memory, provided each row is filled from left to right.
On an empty grid, the count is C(rows + cols - 2, rows - 1).
Compute the binomial with Pascal's additions to avoid overflow in the intermediate values.
Once any cell is blocked, the formula no longer applies, and the table is the method to use.

Unique paths with obstacles and the binomial shortcut

Why this matters

The problem in plain words

The idea: count the routes into each cell

Worked example 1: the 3 by 3 grid with a blocked centre

The first program

Worked example 2: keeping one row at a time

The binomial shortcut for an open grid

Computing the binomial without overflow

Why the formula stops working with obstacles

Common mistakes

Practice

Summary

Stuck? Ask the tutor