Unique Paths II

You are given an M x N grid where each cell is either 0 (free) or 1 (obstacle). Your task is to determine the number of unique paths from the top-left corner (cell (0,0)) to the bottom-right corner (cell (M-1,N-1)). You can only move either down or right at any point in time.

If a cell contains an obstacle (represented by 1), you cannot step on that cell. Otherwise, a cell with 0 is free to use. The dynamic programming recurrence used to solve this problem is given by $$ \text{dp}[i][j] = \begin{cases} 0, & \text{if } grid[i][j]=1,\\ \text{dp}[i-1][j] + \text{dp}[i][j-1], & \text{if } grid[i][j]=0, \end{cases} $$ with the base condition \(\text{dp}[0][0] = 1\) if the starting cell is free; otherwise, the result is 0 if the start is blocked.

Your program should read the grid from standard input and output the number of unique paths to standard output.

inputFormat

The first line of input consists of two integers M and N separated by a space, where M is the number of rows and N is the number of columns in the grid.

This is followed by M lines, each containing N integers (each 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, avoiding obstacles.

3 3
0 0 0
0 1 0
0 0 0

2