Unique Paths II

Given an m × n grid where each cell is either 0 (free) or 1 (obstacle), determine the number of unique paths a robot can take to move from the top-left corner to the bottom-right corner. The robot may only move either down or right at any step.

You can compute the number of paths using the recurrence relation: $$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$ if the current cell is free. If a cell contains an obstacle (i.e. the value is 1), then no path can pass through it. Also, if the starting cell or the ending cell is blocked, the answer is 0.

inputFormat

The first line contains two integers m and n — the number of rows and columns of the grid, respectively. The following m lines each contain n integers (either 0 or 1) separated by spaces, representing the grid. The value 0 indicates a free cell, while 1 indicates an obstacle.

outputFormat

Output a single integer denoting the number of unique paths from the top-left corner to the bottom-right corner while avoiding obstacles.## sample

3 3
0 0 0
0 0 0
0 0 0

6