Unique Paths with Obstacles

You are given an n x m grid represented by integers. Each cell in the grid is either walkable (denoted by 0) or an obstacle (denoted by 1). Your task is to determine the number of unique paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,m)). You are only allowed to move either to the right or downward at any cell.

If a cell contains an obstacle, you cannot move through that cell. Formally, let \(dp[i][j]\) be the number of unique paths to cell \((i,j)\). Then, if the cell \((i,j)\) is free (i.e. it has a 0), the recurrence is given by:

[ dp[i][j] = \begin{cases} dp[i-1][j] + dp[i][j-1] & \text{if } grid[i][j] = 0,\ 0 & \text{if } grid[i][j] = 1. \end{cases} ]

The starting cell \((1, 1)\) is initialized to 1 if it is not an obstacle and similarly, the destination cell must also be free; otherwise, the answer is 0.

This problem typically involves dynamic programming and careful handling of edge cases.

inputFormat

The input is given via standard input (stdin) and consists of:

• One line containing two integers n and m (number of rows and columns).
• n subsequent lines, each containing m integers separated by spaces. Each integer is either 0 or 1, where 0 represents a walkable cell and 1 represents an obstacle.

outputFormat

Output via standard output (stdout) a single integer: the number of unique paths from the top-left corner to the bottom-right corner of the grid.

3 3
0 0 0
0 1 0
0 0 0

2