Distinct Paths in a Grid

You are given an n x n grid where each cell is either open or blocked. The grid is represented by n lines of input, where each line contains n numbers separated by spaces. A '0' denotes an open cell, and a '1' denotes a blocked cell.

Your task is to count the number of distinct paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,n)), moving only right or down at each step. If the starting cell or the ending cell is blocked, then the answer is 0.

You can use the following recurrence relation (in \( \LaTeX \)) for a cell \( (i,j) \) that is open: \[ dp[i][j] = dp[i-1][j] + dp[i][j-1] \] with the base condition \( dp[0][0] = 1 \).

inputFormat

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

• The first line contains an integer n (1 ≤ n ≤ 1000), the size of the grid.
• The next n lines each contain n space-separated digits ('0' or '1') representing the grid.

outputFormat

Output a single integer to standard output (stdout) which represents the number of distinct paths from the top-left corner to the bottom-right corner of the grid.

3
0 0 0
0 1 0
0 0 0

2