Counting paths on grids

Why this matters when you build with AI

Grid path problems show up in contests as robot, delivery and city-map tasks. Give an AI tool the sentence "count the routes from the top-left cell to the bottom-right cell of an H by W grid, moving only right or down, avoiding some cells", and it usually writes a table DP that fills one cell at a time. That is correct for a 10 by 10 grid. With H and W near 200000, the table has 4 times 10^10 cells, which does not fit in memory and does not finish in time.

The fix is a formula with a few special cases, and the special cases are where AI code breaks. A blocked cell can sit on the start, a forced point can lie outside the path's box, and a reflection formula has a side where it is valid. Generated code often passes the samples and fails these cases. The check that catches them is a brute force on small grids and a random stress test. Both are in this lesson.

The code is C++17. We compiled it with g++ -std=c++17 -O2 -Wall -Wextra using GCC 15.2.0 on Linux under WSL2. The output lines below come from those runs. The numbers do not depend on the machine, but the timings do, and we say so where they appear.

Definitions

A cell is written (r, c). Here r is the row counted from the top, and c is the column counted from the left. Rows and columns start at 1, so (1, 1) is the top-left cell.

A monotone path moves only right (column plus 1) or down (row plus 1). It never goes back. Every monotone path from (1, 1) to (H, W) makes exactly H - 1 down moves and W - 1 right moves, in some order.

A blocked cell is a cell the path may not enter. A forced point is a cell every counted path must visit.

The binomial coefficient C(n, k) is the number of ways to choose k positions out of n. For example, C(4, 2) is 6, because the four positions 1, 2, 3, 4 have six pairs. The first lesson of this module covers how to compute C(n, k) modulo a prime.

Reflection is a counting trick. To count paths that touch a line, you mirror the start point across the line and count paths from the mirror point. The idea is explained below with a worked example.

Open grids: the binomial formula

Start with a 3 by 3 grid and a path from (1, 1) to (3, 3). The path makes 2 down moves and 2 right moves. Write each path as a word of four letters with two D and two R. There are six such words, and each one is a valid path:

DDRR, DRDR, DRRD, RDDR, RDRD, RRDD

In general, a path from (r1, c1) to (r2, c2) makes dr = r2 - r1 down moves and dc = c2 - c1 right moves. The number of paths is C(dr + dc, dr). If the target is above or to the left of the start, dr or dc is negative and the count is 0.

For the 3 by 3 grid, dr = 2 and dc = 2, so the count is C(4, 2) = 6, which matches the list.

Paths through forced points

Suppose every path must visit a point P. Each monotone path visits P at most once, because it never goes back to a cell it has left. So each path through P splits into two parts: a path from the start to P, then a path from P to the end. Every pair of such parts gives one path. The count is:

ways(start, P) times ways(P, end)

Take the 3 by 3 grid again and require the cell (2, 2). The count is C(2, 1) times C(2, 1), which is 2 times 2, or 4. To check, look at the six words. The paths that pass (2, 2) are the ones whose first two letters are DR or RD and whose last two letters are DR or RD. That gives 2 times 2 = 4. The other two words, DDRR and RRDD, go around the corners through (3, 1) and (1, 3).

A second check: from (0, 0) to (3, 3) through (1, 2). ways((0, 0), (1, 2)) is C(3, 1) = 3, and ways((1, 2), (3, 3)) is C(3, 1) = 3. The product is 9. We also enumerated all 20 paths from (0, 0) to (3, 3) with a short recursive program, and 9 of them pass through (1, 2). The enumeration and the product agree.

If several forced points must be visited in a fixed order, multiply the counts for each consecutive pair. If the order is not fixed, the problem is harder and needs a different method, and this lesson does not cover it.

Avoiding a line by reflection

Now the diagonal case. Use coordinates (x, y) with x the number of right moves and y the number of up moves, starting at (0, 0). Count paths to (n, m) that never touch the line y = x + 1. In words: the path must always have y at most x.

Define d = y - x. A right move lowers d by 1, and an up move raises it by 1. The path starts at d = 0. The bad event is that d reaches 1. Because d moves in steps of 1, a path that gets to d = 1 must land on it exactly, so the line cannot be jumped over.

Take the bad paths, those that touch the line. Mirror their start point (0, 0) across the line y = x + 1. The mirror of (x, y) across y = x + 1 is (y - 1, x + 1), so (0, 0) becomes (-1, 1). Now match each bad path with a path from (-1, 1) to (n, m). Cut the bad path at its first touch of the line, mirror the part before the cut, and keep the rest. This gives a path from (-1, 1) to (n, m) that must also touch the line. Going the other way is the same operation, so the match is one to one. When m is at most n, every path from (-1, 1) to (n, m) touches the line on the way, because it starts above the line and ends on or below it. So the two sets have the same size.

A path from (-1, 1) to (n, m) makes n + 1 right moves and m - 1 up moves. So there are C(n + m, n + 1) of them. The good paths are all paths minus the bad ones:

good(n, m) = C(n + m, n) - C(n + m, n + 1)

Check with n = m = 2. The formula gives C(4, 2) - C(4, 3) = 6 - 4 = 2. The two good paths are RRUU and RURU. Look at d along RRUU: it goes 0, -1, -2, -1, 0, and never reaches 1. The other four words, UURR, URRU, URUR and RUUR, reach d = 1, so they are bad.

For n = m = 3 the formula gives C(6, 3) - C(6, 4) = 20 - 15 = 5. This number is the Catalan number C_3. The module lesson named "Catalan, Stirling and Bell numbers" covers that family.

The formula has a side. It is valid only when the end point is on or below the line, that is when m is at most n. If the end point is above the line, every path touches the line, so the answer is 0. The formula does not know this, and it gives a negative number. For n = 0 and m = 2, the formula gives C(2, 0) - C(2, 1) = 1 - 2 = -1. The correct answer is 0. Check the side of the end point before you use the formula.

The program below prints the formula and a plain DP that forbids the line, for every pair with m at most n up to 14. It also prints the trap case.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
// Exact binomial for small n (n up to about 60).
ll binom(int n, int k) {
    if (k < 0 || k > n) return 0;
    ll r = 1;
    for (int i = 1; i <= k; i++) r = r * (n - k + i) / i;
    return r;
}
 
// Paths from (0,0) to (n,m) with right and up steps that never touch y = x + 1.
// Valid when m <= n. The formula gives a negative number when m > n.
ll formula(int n, int m) {
    return binom(n + m, n) - binom(n + m, n + 1);
}
 
// Plain DP that forbids the cells on the line y = x + 1. This is the check.
ll dp_count(int n, int m) {
    vector<vector<ll>> d(n + 1, vector<ll>(m + 1, 0));
    for (int x = 0; x <= n; x++)
        for (int y = 0; y <= m; y++) {
            if (y == x + 1) continue;
            if (x == 0 && y == 0) {
                d[x][y] = 1;
                continue;
            }
            if (x > 0) d[x][y] += d[x - 1][y];
            if (y > 0) d[x][y] += d[x][y - 1];
        }
    return d[n][m];
}
 
int main() {
    cout << "n m formula dp\n";
    for (int n = 0; n <= 4; n++)
        for (int m = 0; m <= n; m++)
            cout << n << " " << m << " " << formula(n, m) << " " << dp_count(n, m) << "\n";
 
    bool ok = true;
    for (int n = 0; n <= 14; n++)
        for (int m = 0; m <= n; m++)
            if (formula(n, m) != dp_count(n, m)) ok = false;
    cout << "all pairs with m <= n up to 14 match: " << (ok ? "yes" : "no") << "\n";
 
    cout << "trap, end point above the line (n=0, m=2): formula " << formula(0, 2)
         << ", dp " << dp_count(0, 2) << "\n";
}

The output of this program, as we ran it:

n m formula dp
0 0 1 1
1 0 1 1
1 1 1 1
2 0 1 1
2 1 2 2
2 2 2 2
3 0 1 1
3 1 3 3
3 2 5 5
3 3 5 5
4 0 1 1
4 1 4 4
4 2 9 9
4 3 14 14
4 4 14 14
all pairs with m <= n up to 14 match: yes
trap, end point above the line (n=0, m=2): formula -1, dp 0

Obstacles: sort the blocked cells, then subtract

Now the main problem. The grid is H by W, with K blocked cells. We want the number of monotone paths from (1, 1) to (H, W) that avoid every blocked cell. K can be a few thousand, and H and W can be 200000.

There is no formula for arbitrary blocked cells. The method is to count all paths and remove the bad ones, one blocked cell at a time. The idea is this.

The number of paths from the start to a cell p is ways(start, p), with no blocked cells. This is the open-grid formula.
A path to p that touches a blocked cell has a first blocked cell, the first one it meets. Group the bad paths by that first cell i.
Let f(i) be the number of paths from the start to blocked cell i that touch no other blocked cell before i. The bad paths with first blocked cell i are the f(i) paths to i, followed by any path from i to p. So there are f(i) times ways(i, p) of them.
The paths to p that avoid all blocked cells are ways(start, p) minus the sum of f(i) times ways(i, p), over all blocked cells i.
To find f(i) itself, use the same rule with p = i. Subtract the paths to i that first touch some earlier blocked cell j, which is f(j) times ways(j, i).

The answer is step 4 with p = (H, W).

To compute f in the right order, sort the blocked cells by (row, column). If ways(j, i) is not zero, then j is at or above and at or left of i, so j is earlier in this sort. When f(i) is computed, every f(j) it needs is already known.

Worked example. Take a 4 by 4 grid, with blocked cells (2, 3) and (3, 2). Count paths from (1, 1) to (4, 4). Sorted order: (2, 3), then (3, 2).

Total paths to (4, 4): C(6, 3) = 20.
f((2, 3)) = ways((1, 1), (2, 3)) = C(3, 1) = 3. No blocked cell comes before it.
f((3, 2)) = ways((1, 1), (3, 2)) minus f((2, 3)) times ways((2, 3), (3, 2)). The first term is C(3, 2) = 3. The second is 3 times 0, since column 2 is left of column 3, so ways is 0. So f((3, 2)) = 3.
The paths from each blocked cell to the end: ways((2, 3), (4, 4)) = C(3, 1) = 3, and ways((3, 2), (4, 4)) = C(3, 1) = 3.
Answer = 20 minus 3 times 3 minus 3 times 3, which is 2.

Check by hand. The two paths that avoid both cells are RRRDDD, which goes along the top and right edges, and DDDRRR, which goes along the left and bottom edges. Every other path enters (2, 3) or (3, 2). For example RDRD goes (1, 1), (1, 2), (2, 2), (2, 3), which is blocked.

The code below does this. It sorts the cells, computes f, and prints the answer. The factorial table is built once for size H + W. The constraint H + W below the modulus 998244353 keeps every factorial nonzero, the same trap as in the factorial module.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
 
ll pw(ll a, ll e) {
    ll r = 1;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}
 
// Factorials and inverse factorials up to n, with n < MOD.
struct Binom {
    vector<ll> f, fi;
    explicit Binom(int n) : f(n + 1), fi(n + 1) {
        f[0] = 1;
        for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % MOD;
        fi[n] = pw(f[n], MOD - 2);
        for (int i = n; i >= 1; i--) fi[i - 1] = fi[i] * i % MOD;
    }
    ll C(ll n, ll k) const {
        if (k < 0 || k > n) return 0;
        return f[n] * fi[k] % MOD * fi[n - k] % MOD;
    }
};
 
int main() {
    ll H, W;
    int K;
    cin >> H >> W >> K;
    vector<pair<ll, ll>> blocked(K);
    for (auto& [r, c] : blocked) cin >> r >> c;
 
    // Sorting by (row, column) puts every blocked cell after the blocked cells
    // that lie above it or to its left, which is the order the DP needs.
    sort(blocked.begin(), blocked.end());
 
    Binom T(H + W);
 
    // Number of right and down paths from (r1, c1) to (r2, c2), 0 if unreachable.
    auto ways = [&](ll r1, ll c1, ll r2, ll c2) -> ll {
        if (r2 < r1 || c2 < c1) return 0;
        return T.C((r2 - r1) + (c2 - c1), r2 - r1);
    };
 
    // dp[i] = paths from (1,1) to blocked cell i that touch no other blocked cell.
    vector<ll> dp(K);
    for (int i = 0; i < K; i++) {
        ll v = ways(1, 1, blocked[i].first, blocked[i].second);
        for (int j = 0; j < i; j++) {
            v -= dp[j] * ways(blocked[j].first, blocked[j].second, blocked[i].first, blocked[i].second) % MOD;
        }
        dp[i] = ((v % MOD) + MOD) % MOD;
    }
 
    // Paths to the end that avoid all blocked cells: all paths, minus those
    // whose first blocked cell is cell j.
    ll ans = ways(1, 1, H, W);
    for (int j = 0; j < K; j++) {
        ans -= dp[j] * ways(blocked[j].first, blocked[j].second, H, W) % MOD;
    }
    ans = ((ans % MOD) + MOD) % MOD;
    cout << ans << "\n";
}

Sample runs, as we ran them:

$ printf "3 3 1\n2 2\n" | ./grid_obstacles
2
$ printf "2 2 0\n" | ./grid_obstacles
2
$ printf "1 1 0\n" | ./grid_obstacles
1
$ printf "4 4 2\n2 3\n3 2\n" | ./grid_obstacles
2

The first line checks the center block of a 3 by 3 grid: 6 paths in total, and 4 of them pass the center. The last line is the worked example above.

We tested this program against a brute force. The brute force walks every path with a depth-first search on grids up to 7 by 7 with up to 8 blocked cells. We ran 500 random cases, and all of them matched. We also ran one case of 200000 by 200000 with 3000 blocked cells. It finished in about 0.07 seconds on our machine. Your timing will differ.

Complexity

Factorial table: O(H + W) time and memory.
Blocked cells: O(K^2) time, because each cell is compared with each earlier cell. With K = 3000 that is about 4.5 million pairs, each with a few multiplications.
Memory: O(H + W + K).

The grid itself is never built. That is the point. The cost depends on K and on the size of the factorial table, not on H times W.

Common mistakes

Sorting by the row only. Sorting with a comparison on the first coordinate alone leaves blocked cells in the same row in input order. Then a cell can be processed before a blocked cell to its left in the same row, so f is computed wrong. Input 3 3 2, then 2 3, then 2 1, has answer 1. The version that sorts by the row only printed 0. A random stress test with the same bug printed MISMATCH 2 7 [(1, 7), (1, 2), (2, 2), (2, 6), (2, 5)] got 998244352 want 0. The value 998244352 is minus one modulo 998244353. The wrong order made a negative total, and the final reduction turned it into this large positive number. Sort the pairs as pairs, not by one coordinate.

Forgetting the subtraction. If the blocked cells are ignored, the answer for the worked example is the total 20, not 2. A program that only prints ways(1, 1, H, W) passes samples with no blocked cells and fails every other case.

Negative numbers after the modulus. In C++, % keeps the sign of the left side. So -5 % 3 is -2, not 1. Every subtraction must be followed by ((x % MOD) + MOD) % MOD. Without that line, the answer can be negative.

The reflection formula on the wrong side. For the diagonal count, the formula with m greater than n prints -1 for n = 0, m = 2. The true answer is 0. Check the end point first.

A factorial table that is too small. The table must reach H + W, the largest value of dr + dc. A table of size max(H, W) reads past the end of the vector. C++ does not check this, so the program can print any value, or crash, depending on the machine.

Testing only the samples. The samples are small and easy. Two of the bugs above pass every sample. Run the brute force on random grids before you trust the code.

A prompt to check AI output

Use this prompt on the program an AI tool gives you. Paste your code in the place of the marker.

Here is a C++ program that counts right and down paths from (1,1) to (H,W) in a grid,
avoiding K blocked cells. Check it for these three things and name the line number for each:
1. The order in which the blocked cells are processed. Is it guaranteed that every
   blocked cell that can reach cell i is processed before cell i?
2. Negative values after the % operator. Is every final answer reduced into [0, MOD)?
3. The factorial table size. Does it reach H + W, and is H + W below the modulus?
Then write a Python brute force that enumerates all paths for grids up to 6 by 6, and a
random test that compares the program with it on 300 cases. Print any mismatch with its input.

A good answer names a line for each check, and says why the line is right or wrong. It also gives a test you can run. An answer that only says "the code looks correct" has not checked anything.

Checklist

Is the path type stated in the problem (right and down, or right and up), and does the code use it?
Are the coordinates 1-based in the statement and in the code?
Are the blocked cells sorted as pairs before the DP runs?
Is every subtraction followed by a reduction into [0, MOD)?
Does the factorial table reach H + W, and is H + W below the modulus?
For a reflection formula, is the end point on the valid side of the line?
Did the code match a brute force on at least 200 random small grids?

Exercise: a checkpoint on a huge grid

Write a program for this problem. It is an original problem for this course.

A delivery drone starts at the top-left cell (1, 1) of a grid with H rows and W columns. It finishes at the bottom-right cell (H, W). Each move takes it one cell right or one cell down. Some cells hold radio towers, and the drone may not enter a tower. The drone must also pass through a depot cell P. Count the routes that meet all these rules, and print the count modulo 998244353.

Input:

Line 1: H W K, with 1 at most H and W, H + W at most 400000, and 0 at most K at most 3000.
Next K lines: the row and column of each tower. The towers are distinct, and none is at (1, 1), (H, W) or P.
Last line: the row and column of the depot P, inside the grid.

Output: one integer.

Sample 1:

Sample 1 output: 0. The two routes that avoid the towers do not visit (3, 3).

Sample 2:

Sample 2 output: 1. Only RRRDDD goes through (1, 4) and avoids the towers.

Hint: a route through P is a route from the start to P, followed by a route from P to the end. Both parts must avoid the towers. You already have a function that counts routes avoiding blocked cells. Make it take a start cell and an end cell as arguments, then multiply the two counts.

Show the answer

The solution is the program below. It calls the obstacle count twice, once for the start to P and once for P to the end, and multiplies the results. It reads the same input format as the samples. We compiled it with g++ -std=c++17 -O2 -Wall -Wextra and ran both samples, which printed 0 and 1. We also compared it with a brute force that enumerates all routes on 400 random grids up to 7 by 7, with up to 7 towers and a random depot. All 400 matched. On a 200000 by 200000 grid with 3000 towers and a depot at (100000, 100000), it printed a value and took about 0.14 seconds on our machine. Your timing will differ.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Cell = pair<ll, ll>;
const ll MOD = 998244353;
 
ll pw(ll a, ll e) {
    ll r = 1;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}
 
struct Binom {
    vector<ll> f, fi;
    explicit Binom(int n) : f(n + 1), fi(n + 1) {
        f[0] = 1;
        for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % MOD;
        fi[n] = pw(f[n], MOD - 2);
        for (int i = n; i >= 1; i--) fi[i - 1] = fi[i] * i % MOD;
    }
    ll C(ll n, ll k) const {
        if (k < 0 || k > n) return 0;
        return f[n] * fi[k] % MOD * fi[n - k] % MOD;
    }
};
 
// Right and down paths from a to b, 0 when b is not reachable from a.
ll ways(const Binom& T, Cell a, Cell b) {
    if (b.first < a.first || b.second < a.second) return 0;
    return T.C((b.first - a.first) + (b.second - a.second), b.first - a.first);
}
 
// Paths from s to t avoiding every blocked cell. blocked must be sorted.
ll count_avoid(const Binom& T, Cell s, Cell t, const vector<Cell>& blocked) {
    vector<ll> dp(blocked.size());
    for (size_t i = 0; i < blocked.size(); i++) {
        ll v = ways(T, s, blocked[i]);
        for (size_t j = 0; j < i; j++) v -= dp[j] * ways(T, blocked[j], blocked[i]) % MOD;
        dp[i] = ((v % MOD) + MOD) % MOD;
    }
    ll ans = ways(T, s, t);
    for (size_t j = 0; j < blocked.size(); j++) ans -= dp[j] * ways(T, blocked[j], t) % MOD;
    return ((ans % MOD) + MOD) % MOD;
}
 
int main() {
    ll H, W;
    int K;
    cin >> H >> W >> K;
    vector<Cell> blocked(K);
    for (auto& c : blocked) cin >> c.first >> c.second;
    Cell P;
    cin >> P.first >> P.second;
    sort(blocked.begin(), blocked.end());
 
    Binom T(H + W);
    // A monotone path visits P at most once, so the paths through P are exactly
    // (start to P, avoiding blocked cells) followed by (P to end, avoiding blocked cells).
    ll ans = count_avoid(T, {1, 1}, P, blocked) * count_avoid(T, P, {H, W}, blocked) % MOD;
    cout << ans << "\n";
}

Summary

Monotone paths on an open grid are binomial coefficients. A forced point splits the count into two parts that multiply. A diagonal is removed by mirroring the start point, and the formula only holds on one side of the line. Blocked cells are removed by sorting them, computing the paths to each one that avoid the others, and subtracting.

Practice

Each practice problem has a hint. Try it before you read the answer under the line "Show the answer".

Count the monotone paths from (1, 1) to (5, 7) on an open grid. Hint: find dr and dc first.

Show the answer dr = 4 and dc = 6, so the count is C(10, 4) = 210.

Count the paths from (0, 0) to (4, 4) with right and up steps that never touch the line y = x + 1. Hint: use the reflection formula with n = 4 and m = 4.

Show the answer The count is C(8, 4) - C(8, 5) = 70 - 56 = 14. This is the Catalan number C_4. The reflection program prints 14 for n = 4, m = 4 in its table.

A 3 by 3 grid has one blocked cell at (2, 2). Count the paths from (1, 1) to (3, 3). Hint: 6 paths exist in total. How many pass through (2, 2)?

Show the answer Four paths pass through (2, 2), because ways((1, 1), (2, 2)) is 2 and ways((2, 2), (3, 3)) is 2, so 2 times 2 is 4. The answer is 6 minus 4, which is 2. The two valid paths are DDRR, which goes down the left edge, and RRDD, which goes along the top edge.

A 3 by 4 grid has blocked cells (2, 2) and (2, 3). Count the paths from (1, 1) to (3, 4). Hint: a path that avoids both cells in row 2 must enter row 2 and leave it through the columns 1 and 4 only.

Show the answer The answer is 2. The total is C(5, 2) = 10. A path that avoids both cells must use row 2 only at column 1 or only at column 4. Those two paths are DDRRR, which goes down at column 1, and RRRDD, which goes down at column 4. In every other path, the cells it visits in row 2 include column 2 or column 3. The obstacle formula gives the same answer: f((2, 2)) = 2, f((2, 3)) = 3 - 2 = 1, and 10 - 2 times 3 - 1 times 2 = 2.

A 5 by 5 grid has no blocked cells. Count the paths from (1, 1) to (5, 5) that pass through (3, 3). Hint: this is a forced point with no blocked cells.

Show the answer Each half has C(4, 2) = 6 paths, so the count is 6 times 6 = 36.