Unique Paths in a Grid with Obstacles

You are given a square grid of size n where each cell is either empty (denoted by 0) or contains an obstacle (denoted by 1). Your task is to determine the number of unique paths from the top-left corner to the bottom-right corner of the grid, moving only right or down.

If at the start or the end cell there is an obstacle, then the answer is 0.

The dynamic programming recurrence used is given by the LaTeX formula:

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

Compute and output the number of unique paths.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer n, the size of the grid.
• The next n lines each contain n space-separated integers representing the grid. Each integer is either 0 (empty cell) or 1 (obstacle).

outputFormat

Output a single integer on standard output (stdout), which is the number of unique paths from the top-left cell to the bottom-right cell.

3
0 0 0
0 1 0
0 0 0

2