Unique Paths in a Grid with Obstacles

You are given a square grid of size \(n\) where each cell is either a free cell denoted by . or an obstacle denoted by #. The task is to calculate the number of unique paths from the top-left corner to the bottom-right corner. You can only move either to the right or down. A path is valid if it does not pass through any obstacles.

If there is an obstacle at the starting cell or the destination cell, the answer is \(0\). Otherwise, you can use the recurrence formula:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)

where \(dp[i][j]\) represents the number of unique paths to reach cell \((i, j)\), provided it is not blocked.

inputFormat

The first line contains an integer \(n\) which represents the size of the grid. The following \(n\) lines each contain a string of length \(n\) consisting of characters . (free cell) and # (obstacle).

outputFormat

Output a single integer representing the number of unique paths from the top-left to the bottom-right corner.

3
...
.#.
...

2