Unique Paths with Obstacles

You are given a two-dimensional grid of size (n \times m) containing only the characters '.' (denoting an open cell) and '#' (denoting an obstacle). Starting from the top-left cell (cell (1,1)) and only moving either right or down, your task is to determine the number of unique paths to reach the bottom-right cell (cell (n,m)). If either the starting cell or the destination cell is blocked, or if there is no valid path, output (-1).

A dynamic programming solution can be used with the recurrence relation given by:
[ dp[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = '#'\ dp[i-1][j] + dp[i][j-1], & \text{if } grid[i][j] = '.' \end{cases} ]
with the initialization (dp[0][0] = 1) if the starting cell is not blocked. The final answer is (dp[n-1][m-1]) if it is nonzero, otherwise output (-1).

inputFormat

The input is read from standard input (stdin). The first line contains two space-separated integers (n) and (m), representing the number of rows and columns in the grid respectively. Each of the following (n) lines contains a string of length (m) consisting of the characters '.' and '#' that represent a grid row.

outputFormat

Output a single integer to standard output (stdout): the total number of unique paths from the top-left to the bottom-right of the grid. If there is no valid path, output (-1).## sample

3 3
...
.#.
...

2