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 m and n (rows and columns).
Next m lines: each contains n space-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).)

Output

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

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…