149. Rat in a Maze - Count Distinct Paths

A rat starts at the top-left cell of an n x n maze and must reach the bottom-right cell, moving only right or down, and only through cells marked 1 (cells marked 0 are blocked). Count the number of distinct such paths.

Input: The first line contains an integer n. The next n lines each contain n space-separated integers (0 or 1) representing the maze. Output: Print a single integer - the number of distinct paths from the top-left to the bottom-right cell moving only right or down through open cells.

1 <= n <= 100

A blocked START or END cell (if input allowed such a case) would immediately make the answer 0 - a quick sanity check worth keeping in mind even though this specific problem's example doesn't test it directly.

Count how many distinct paths exist from a maze's top-left to bottom-right, moving only right or down through open cells. Brute force: Use pure backtracking, recursively trying right and down moves and counting how many recursive calls reach the destination - this works correctly but can recompute the SAME sub-path counts repeatedly when multiple routes pass through the same cell, especially on larger grids (n up to 100 makes this recomputation costly without memoization). Optimised: Converting the backtracking recursion into a bottom-up DP table means each cell's path-count is computed exactly once, reused directly by every cell that could reach it - turning potentially exponential re-exploration into a clean O(n²) table fill.

Use the exact same recursive relation as the brute approach, but store the result for each (row, col) pair in a memo table the first time it's computed, and simply return the cached value on any later request for that same cell. Since every one of the n^2 cells now has its path count computed only once, the exponential blowup disappears and the total work becomes proportional to the number of cells in the maze. Time: O(n^2) Space: O(n^2)

Fill an n x n table iteratively from the top-left down: dp[row][col] is 0 if the cell is blocked, otherwise it's the sum of dp[row-1][col] (arriving from above) and dp[row][col-1] (arriving from the left), with dp[0][0] set to 1 if that cell is open; the answer is dp[n-1][n-1]. Since each row only ever depends on the row directly above it, the table can be computed while keeping just a single rolling row in memory instead of the full n x n grid, cutting the space usage down substantially while keeping the same linear-per-cell work. Time: O(n^2) Space: O(n) (single rolling row)

Define recurse(row, col) as the number of distinct paths from that cell to the bottom-right, using the relation recurse(row, col) = recurse(row+1, col) + recurse(row, col+1) whenever the current cell is open (1), with 0 returned immediately for blocked cells or out-of-bounds positions, and 1 at the destination. Because different root-to-cell paths reach the same (row, col) repeatedly, this recomputes the same subproblem's path count many times over, causing the total work to grow combinatorially with the maze size. Time: Exponential (up to O(2^n) roughly) Space: O(n) recursion depth

1. Build a DP table where dp[i][j] is the number of ways to reach cell (i,j) moving only right or down through open cells. 2. If the cell itself is blocked, dp[i][j] is immediately 0. 3. Otherwise, dp[i][j] is the sum of the ways to reach it from above (dp[i-1][j]) and from the left (dp[i][j-1]).

Time: O(n²) - filling the DP table, one cell at a time. Space: O(n²) for the full table (reducible to O(n) with a rolling 1D array, since each row only depends on the row above it).

Test n = 1, a maze where the start or end cell is blocked (0 paths), and n = 100 for performance.

Be ready to explain the direct connection between this DP solution and the 'backtracking that would explore every path individually' - recognizing that DP here is really just 'memoized backtracking' reframed as a table-filling process.