Maze path counting

Overview

Grid recursion comes in two flavours that differ by one crucial detail: whether a cell can be revisited. Monotone movement (right and down only) can never return to a cell, so no bookkeeping is needed — just sum the two moves. Free 4-directional movement can loop forever unless you mark a cell on the way in and unmark it on the way out; that mark-and-unmark is backtracking applied to a grid. Forgetting the unmark does not cause a hang — it silently under-counts, because cells stay blocked for sibling branches that should have been free to use them.

Why it matters

Grid search is the foundation of maze solving, flood fill, connected-component labelling, and pathfinding in games and robotics. The distinction between "cannot revisit by construction" and "must prevent revisiting explicitly" appears in every graph traversal you will write, and the mark/unmark asymmetry — unmark for path enumeration, keep marked for reachability — is a genuinely subtle point worth getting right once.

Core concepts

Monotone (right/down) counting. paths(i,j) = paths(i+1,j) + paths(i,j+1), with the destination returning 1 and any out-of-bounds or blocked cell returning 0. Because every move increases i + j, a cell can never be revisited — no visited array is required.

4-directional search. Now revisiting is possible, so the cell must be marked before recursing into the four neighbours and unmarked afterwards. Without the mark, the recursion cycles forever between two adjacent cells.

Mark and unmark — and when not to unmark. For counting simple paths, unmark on the way out so other branches may use the cell. For reachability or flood fill, deliberately do not unmark: each cell should be visited once and the whole point is to avoid repeats.

Bounds before contents. The guard must test i < 0 || i >= r || j < 0 || j >= c before reading g[i*c + j], or an out-of-range index is dereferenced. C's || short-circuits left to right, which makes this ordering safe.

Exponential blowup. Counting simple paths in a grid is exponential; the monotone version, by contrast, is a DP with C(r+c-2, r-1) paths that you have already met in the grid-DP lesson.

Syntax notes

/* monotone: no visited array needed - i+j always increases */
int mp(const int *g, int r, int c, int i, int j) {
    if (i >= r || j >= c || g[i*c + j]) return 0;   /* off-grid or blocked */
    if (i == r-1 && j == c-1) return 1;             /* reached the goal */
    return mp(g,r,c,i+1,j) + mp(g,r,c,i,j+1);
}

/* 4-directional: MUST mark and unmark */
int dfs(int *g, int n, int i, int j) {
    if (i < 0 || i >= n || j < 0 || j >= n) return 0;   /* bounds FIRST */
    if (g[i*n + j]) return 0;                          /* blocked or already on this path */
    if (i == n-1 && j == n-1) return 1;
    g[i*n + j] = 1;                                    /* mark: on the current path */
    int t = dfs(g,n,i+1,j) + dfs(g,n,i-1,j)
          + dfs(g,n,i,j+1) + dfs(g,n,i,j-1);
    g[i*n + j] = 0;                                    /* UNMARK: restore for siblings */
    return t;
}

Key points:

• Bounds checks must precede the array read; || short-circuits so this is safe.
• Unmark for path counting; keep the mark for reachability/flood fill.
• The 4-directional version mutates the caller's grid, so it cannot take const.

Lesson

Counting maze paths shows two flavours of grid recursion: monotone right/down movement (no revisiting needed) versus full 4-directional search that must mark cells visited and unmark on backtrack to count simple paths.

Code examples

#include <stdio.h>
static int mp(const int*g,int r,int c,int i,int j){ if(i>=r||j>=c||g[i*c+j]) return 0; if(i==r-1&&j==c-1) return 1; return mp(g,r,c,i+1,j)+mp(g,r,c,i,j+1); }
static int dfs(int*g,int n,int i,int j){ if(i<0||i>=n||j<0||j>=n||g[i*n+j]) return 0; if(i==n-1&&j==n-1) return 1; g[i*n+j]=1; int c=dfs(g,n,i+1,j)+dfs(g,n,i-1,j)+dfs(g,n,i,j+1)+dfs(g,n,i,j-1); g[i*n+j]=0; return c; }
int main(void){
    int grid[]={0,0,0, 0,1,0, 0,0,0};
    printf("right/down paths (block in center) = %d\n", mp(grid,3,3,0,0));
    int open[]={0,0,0, 0,0,0, 0,0,0};
    printf("4-directional simple paths (3x3)   = %d\n", dfs(open,3,0,0));
    return 0;
}

Line by line

Common mistakes

Recursing off the grid; forgetting to unmark visited cells (misses valid paths).

Debugging tips

Compiler errors and warnings:

• warning: passing const int * to int * if you try to pass a const grid to the mutating version — a useful signal that this function writes to the grid.
• No warning for a missing unmark.

Runtime symptoms:

• Infinite recursion / stack overflow in the 4-directional version. The mark is missing, so the search oscillates between two neighbours.
• Path count is too low. The unmark is missing. This is the quiet bug — no crash, just wrong numbers.
• Segfault at the edges. The bounds check runs after (or is missing before) the g[...] read. Order matters.
• Counts wrong on a rectangular grid. The stride is wrong — with r != c, indexing must use i*c + j, not i*n + j.
• Exponential runtime. Expected for simple-path counting; the monotone version is polynomial.

Technique: test a 3x3 open grid — the monotone answer is 6. Then block the centre and confirm it drops to 2. For the 4-directional version, compare a tiny 2x2 grid against a hand count.

Memory safety

• Bounds before dereference. The single most important rule here: i < 0 || i >= r || j < 0 || j >= c must be evaluated before g[i*c + j]. Relying on the array read to "fail" is undefined behaviour, and a negative index reads before the buffer.
• Stride correctness. For an r x c grid the index is i*c + j. Using i*r + j or a mismatched stride reads valid-but-wrong memory — no crash, just corruption of the answer.
• The mutating version changes the caller's data. It must restore every cell it marks; an early return that skips the unmark leaves the grid permanently altered, corrupting all later queries.
• Depth can reach r*c. A 1000x1000 grid means up to a million frames — stack exhaustion. Use an explicit stack or BFS for large grids.
• Exponential runtime on untrusted grid sizes is a denial-of-service risk; bound the input.

Real-world uses

Concrete uses: Maze generation and solving, flood fill in paint tools, connected-component labelling in image processing, reachability checks on tile maps in games, and robot coverage planning. The monotone variant is the recursion behind the grid-DP path counting you have already seen; the 4-directional variant is a depth-first search on an implicit graph.

Professional best practices:

Beginner:

• Write the bounds guard first, then the blocked check, then the goal test.
• Pair every mark with its unmark on the same code path.

Intermediate:

• Decide deliberately whether to unmark: path enumeration yes, reachability no.
• Use a separate visited array rather than mutating the caller's grid when the input must be preserved.
• Convert to BFS or an explicit stack for large grids, both to avoid stack limits and to get shortest paths.

Practice tasks

1. (Beginner) Monotone path count. Implement mp for right/down movement with obstacles. Example: open 3x3 -> 6; centre blocked -> 2. Concepts: monotone movement, no visited array.

2. (Beginner) Bounds ordering. Deliberately move the bounds check after the grid read on a copy of the function and observe the crash under a sanitizer. Concepts: why guard order matters.

3. (Intermediate) 4-directional simple paths. Implement dfs with mark and unmark. Requirements: the grid must be unchanged when the call returns. Concepts: backtracking on a grid.

4. (Intermediate) Reachability vs enumeration. Modify the 4-directional version to answer "is the goal reachable?" by not unmarking, and compare the runtimes. Concepts: when to keep the mark.

Summary

Grid recursion splits on whether revisiting is possible. Right/down movement is monotone — i + j always increases — so no visited tracking is needed and the recursion simply sums the two moves. Free 4-directional movement must mark a cell before recursing and unmark it afterwards; skipping the mark causes infinite recursion, while skipping the unmark silently under-counts because cells stay blocked for sibling branches. Always test bounds before reading the cell, keep the row stride consistent (i*c + j), and remember to keep the mark when you want reachability rather than path enumeration.

Practice with these exercises

• Count maze paths (right/down)
• Count 4-directional simple paths