Grid Navigation with Obstacles (Medium) — Practice with Code Visualizer

You are given an m × n integer matrix called grid. An autonomous agent is initially positioned at the top-left cell (i.e., grid[0][0]) and aims to reach the bottom-right cell (i.e., grid[m-1][n-1]). The agent can only move in two directions at any given moment: rightward (to the adjacent cell in the same row) or downward (to the adjacent cell in the same column).

Within the grid, each cell is marked with either:

0 — indicating an open passable cell
1 — indicating a blocked cell (obstacle) that the agent cannot traverse

The agent's path must consist entirely of open cells; it cannot pass through any blocked cell at any point during navigation.

Your task is to determine the total number of distinct routes the agent can take from the starting position to the destination. A route is considered distinct if the sequence of moves differs from another route, even if both ultimately reach the same destination.

Note: The test cases are designed such that the answer will not exceed 2 × 10⁹.

There is one obstacle in the center of the 3×3 grid. Two distinct paths exist to reach the bottom-right corner:

Move Right → Right → Down → Down
Move Down → Down → Right → Right Both paths successfully avoid the central obstacle.

The top-right cell is blocked. The only valid path is: Down → Right.

With no obstacles, there are two distinct paths: Right → Down and Down → Right.