Grid Paths with Obstacles

This problem asks you to determine the number of ways to reach the bottom-right corner of a grid from the top-left corner. You are given an \( n \times m \) grid in which each cell is either open (represented by a '.') or blocked (represented by a '#'). You can only move either to the right or downward.

More formally, let \(dp[i][j]\) be the number of ways to reach cell \( (i, j) \). The recurrence relation is given by:

\[ dp[i][j] = \begin{cases} dp[i-1][j] + dp[i][j-1] & \text{if } grid[i][j] = '.' \\ 0 & \text{if } grid[i][j] = '#' \end{cases} \]

If the starting cell is blocked, the answer is 0. Similarly, if there is no valid way to reach the bottom-right cell, output 0.

inputFormat

The first line contains two space-separated integers \( n \) and \( m \) representing the number of rows and columns of the grid.

The next \( n \) lines each contain a string of length \( m \) where each character is either a '.' or a '#' denoting an open or a blocked cell respectively.

outputFormat

Output a single integer: the number of different ways to move from the top-left corner to the bottom-right corner of the grid, following the allowed moves.

3 3
...
.#.
...

2