Unique Paths
Real-world version: Grid Courier RoutesThe statement here is our own: the same inputs, outputs and technique.
A bicycle courier works a planned district shaped as m streets running east-west crossed by n streets running north-south, giving m rows and n columns of intersections.
The courier waits at the intersection in the northwest corner, row 1 and column 1, and must deliver to the intersection in the southeast corner, row m and column n. Traffic rules allow exactly two kinds of step: ride one block east, landing on the next column of the same row, or ride one block south, landing on the next row of the same column.
Two routes count as different when the sequence of steps differs. Return how many different routes reach the delivery point.
Examples
Example 1
- Input
- m = 4, n = 5
- Output
- 35
Any route takes 3 southbound blocks and 4 eastbound blocks in some order, and there are 35 such orders.
Example 2
- Input
- m = 1, n = 6
- Output
- 1
A single row leaves no room to ride south, so the only route is five straight eastbound blocks.
Example 3
- Input
- m = 2, n = 2
- Output
- 2
The courier either rides east then south, or south then east.
Constraints
- 1 <= m <= 100
- 1 <= n <= 100
- The district is laid out so that the number of different routes is at most 10^12.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def count_routes(m: int, n: int) -> int:public int countRoutes(int m, int n)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's