Unique Paths with Obstacles

You are given a grid of size n × m where each cell is either free (denoted by 0) or blocked by an obstacle (denoted by 1). Starting from the top-left corner and moving only to the right or down, your task is to count the number of unique paths that lead to the bottom-right corner.

If the starting cell is blocked, then there is no valid path. The recurrence relation used in the dynamic programming solution is given by: \(dp[i][j] = dp[i-1][j] + dp[i][j-1]\) (only when \(grid[i][j] = 0\)); otherwise, \(dp[i][j] = 0\).

inputFormat

The input is read from stdin. The first line contains two integers (n) and (m) representing the number of rows and columns respectively. This is followed by (n) lines, each containing (m) space-separated integers (0 or 1) which represent the grid.

outputFormat

Output to stdout a single integer: the number of unique paths from the top-left corner to the bottom-right corner in the grid.## sample

1 1
0

1