Distinct Paths in a Grid with Obstacles

You are given a square grid of size N × N where each cell can either be free (represented by 0) or contain an obstacle (represented by 1). Your task is to determine the number of distinct paths from the top-left corner of the grid to the bottom-right corner, moving only right or down, and avoiding obstacles.

The problem can be solved using dynamic programming. The recurrence relation is given by: $$dp[i][j] = dp[i-1][j] + dp[i][j-1]$$ with the base condition dp[0][0] = 1 if the starting cell is free, otherwise the number of paths is 0. Cells containing an obstacle contribute 0 to the number of paths.

Compute the number of unique paths for the given grid.

inputFormat

The first line contains an integer N denoting the size of the grid. The next N lines each contain N space-separated integers (either 0 or 1) representing the grid rows.

outputFormat

Output a single integer, the number of distinct paths from the top-left corner to the bottom-right corner of the grid, avoiding obstacles.

2
0 0
0 0

2