Number of Ways to Build a Road

You are given an \( n \times n \) grid where each cell is either empty (denoted by '.') or contains a building (denoted by '#'). You need to compute the number of ways to construct a road from the top-left corner (cell \( (0,0) \)) to the bottom-right corner (cell \( (n-1,n-1) \)).

The road can only be built on empty cells and you can only move right or down. The recurrence relation for the number of ways to reach cell \( (i,j) \) is given by:

[ \text{dp}[i][j] = \text{dp}[i-1][j] + \text{dp}[i][j-1] ]

with the condition that if a cell is blocked (i.e. contains '#'), then no road can pass through it. Also, if the starting cell or the ending cell is blocked, the answer is \( 0 \).

Your task is to implement an algorithm that uses dynamic programming to compute the number of ways to reach the destination.

inputFormat

The first line contains an integer \( n \) \( (1 \leq n \leq 1000) \) representing the size of the grid. The following \( n \) lines each contain a string of length \( n \) consisting of characters '.' and '#'.

Input is provided via standard input (stdin).

outputFormat

Output a single integer representing the number of ways to build the road from the top-left to the bottom-right corner. The output should be printed to standard output (stdout).

3
...
.#.
...

2