Count 4-directional simple paths

Challenge

Implement:

int count_paths_4dir(const int *grid, int n);

Count simple paths (no cell revisited) from top-left to bottom-right of an n x n grid, moving up/down/left/right; cells with value 1 are blocked. 1 <= n <= 5.

Input format

Row-major 0/1 grid, size n.

Output format

Number of simple paths.

Constraints

Mark a cell visited, recurse, then unmark.

Starter code

#include <stddef.h>
/* Count simple paths (no cell revisited) from top-left to bottom-right of an n x n grid, moving up/down/left/right; cells with value 1 are blocked. Backtracking. 1<=n<=5. */
int count_paths_4dir(const int *grid,int n){ (void)grid;(void)n; return 0; }

Common mistakes

Not unmarking on backtrack (misses paths); revisiting cells.

Edge cases to handle

A blocked start or end gives 0.

Background lessons

• Maze path counting