Robot Path Counting with Obstacles

You are given an \(N \times N\) grid representing a map, where each cell is either open (represented by 0) or blocked (represented by 1). A robot starts at the top-left cell \((0, 0)\) and needs to reach the bottom-right cell \((N-1, N-1)\). The robot can only move either to the right or down.

Your task is to determine the number of different valid paths from the starting point to the destination. A path is considered valid if it does not pass through any blocked cell. Note that if either the starting cell or the destination cell is blocked, the output should be 0.

The problem can be solved using dynamic programming. The number of ways to reach a cell \((i, j)\) (if not blocked) is the sum of ways to reach the cell above (\((i-1, j)\)) and the cell to the left (\((i, j-1)\)).

Input Format (stdin):

• 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.

Output Format (stdout):

• Output a single integer indicating the number of valid paths from the top-left cell to the bottom-right cell.

inputFormat

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

outputFormat

Output a single integer indicating the number of valid paths from the top-left cell to the bottom-right cell.## sample

3
0 0 0
0 1 0
0 0 0

2