Count Safe Paths in a Grid

You are given an n x n grid where each cell is either safe (0) or blocked (1). The task is to determine the number of safe paths from the top-left cell to the bottom-right cell. At each step, you may only move right or down. If either the starting cell or the destination cell is blocked, the answer is 0.

This problem can be formulated using dynamic programming. Let \(dp[i][j]\) represent the number of ways to reach cell \((i,j)\). The recurrence relation is given by:

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

Your goal is to calculate \(dp[n-1][n-1]\) given that \(dp[0][0] = 1\) if the starting cell is safe.

inputFormat

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

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

outputFormat

Output a single integer to stdout — the number of safe paths from the top-left to the bottom-right corner of the grid.

3
0 0 1
0 0 1
1 0 0

2