Unique Paths in a Grid with Obstacles

You are given an n x m grid where some cells are passable (denoted by 0) and others contain obstacles (denoted by 1). Starting from the top‐left corner (cell (1,1)) and aiming to reach the bottom‐right corner (cell (n,m)), you can only move either right or down at any step.

Your task is to determine the number of unique paths from the start to the destination while avoiding obstacles.

The problem can be formulated mathematically as follows:

Let \(dp(i,j)\) be the number of ways to reach cell \((i,j)\). If the cell \((i,j)\) is not blocked, then:

\[ \text{dp}(i,j)=\begin{cases} 1 & \text{if } i = 1 \text{ and } j = 1,\\ \text{dp}(i-1,j)+\text{dp}(i,j-1) & \text{otherwise}. \end{cases} \]

If a cell is blocked, then \(dp(i,j) = 0\). Additionally, if the starting cell or ending cell is blocked, there is no valid path, and the answer should be \(0\).

inputFormat

The first line of input contains two integers n and m (1 ≤ n, m ≤ 100) representing the number of rows and columns of the grid respectively.

The following n lines each contain m integers (each being either 0 or 1) separated by spaces, representing the grid.

outputFormat

Output a single integer — the number of unique paths from the top-left corner to the bottom-right corner.

## sample

3 3
0 0 0
0 1 0
0 0 0

2