Grid Traversal Routes (Medium) — Practice with Code Visualizer

An autonomous delivery drone is positioned at the top-left corner of a rectangular warehouse floor grid with m rows and n columns. The drone's mission is to navigate to the bottom-right corner of the grid where the delivery destination is located.

Due to operational constraints, the drone can only move in two directions at any given moment:

Move Down: Advance one row closer to the bottom edge
Move Right: Advance one column closer to the right edge

The drone cannot move up, left, or diagonally. Given the dimensions of the warehouse grid (m x n), calculate the total number of distinct routes the drone can take to reach its destination from the starting position.

Starting position: Cell at row 0, column 0 (top-left corner) Destination: Cell at row m-1, column n-1 (bottom-right corner)

Each unique sequence of moves that successfully leads from start to destination counts as one distinct route.

The input is guaranteed to produce an answer that does not exceed 2 × 10⁹.

The warehouse has 3 rows and 7 columns. The drone must make exactly 2 downward moves and 6 rightward moves to reach the destination. The number of distinct ways to arrange these moves equals the number of routes, which is C(8,2) = 28.

With a 3×2 grid, the drone needs 2 down moves and 1 right move. The three possible routes are:

Right → Down → Down
Down → Right → Down
Down → Down → Right

With a 2×3 grid, the drone needs 1 down move and 2 right moves. The three possible routes are:

Right → Right → Down
Right → Down → Right
Down → Right → Right