#024easyDynamic Programming
Grid Path Counting - Trading Floor Layout
Time Limit: 2sMemory: 256MB
Problem
A trading floor is laid out as an m x n grid. You need to walk from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1). You can only move right or down at each step.
Some cells are blocked by equipment (marked as 1), and you cannot step on them. Open cells are marked as 0.
Find the number of unique paths from the top-left to the bottom-right corner.
Input Format
- First line: two integers
mandn(rows and columns). - Next
mlines: each containsnspace-separated integers (0 or 1).
Output Format
A single integer representing the number of unique paths. If no path exists, output 0.
Examples
Example 1
Input(First line: two integers m and n (rows and columns).)
3 3 0 0 0 0 1 0 0 0 0
Output
2
3x3 grid with center blocked. Two paths: right-right-down-down and down-down-right-right.
Example 2
Input(First line: two integers m and n (rows and columns).)
2 2 0 0 0 0
Output
2
2x2 grid with no obstacles. Paths: right-down and down-right.
Constraints
- •1 ≤ m, n ≤ 100
- •grid[i][j] is 0 (open) or 1 (blocked)
Loading interactive editor…