Rat in a Maze

Guide the rat from start to goal, avoiding walls, using backtracking.

backtracking recursion maze grid

You are given a maze represented as a 2D list of integers: 0 means a free cell, 1 means a wall. A rat starts at the top-left corner (0, 0) and needs to reach the bottom-right corner (rows-1, cols-1). The rat can only move down or right (no diagonals, no left/up). If the start or goal cell is a wall (1), the rat cannot move at all — the answer is 0. Write a function `count_paths(maze)` that returns the number of distinct paths from start to goal. The number of paths may be large, so return the count modulo 1_000_000_007.

Constraints

- 1 <= len(maze) <= 20
- 1 <= len(maze[0]) <= 20
- maze[i][j] is 0 or 1
- Expected time complexity: O(rows * cols).
- Use recursion with memoization or dynamic programming.

Example

>>> count_paths([[0, 0, 0], [0, 1, 0], [0, 0, 0]])
2
>>> count_paths([[0, 1], [0, 0]])
1
>>> count_paths([[1, 0], [0, 0]])
0
>>> count_paths([[0, 0], [0, 0]])
2

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Define a recursive function f(i, j) that returns the number of ways from cell (i, j) to the goal.

Base case: if (i, j) is the goal, return 1. If out of bounds or maze[i][j] == 1, return 0.

Use memoization (e.g., a 2D list) to avoid recomputation; only two moves are possible (down, right).

Take modulo 1_000_000_007 at each addition.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.