Unique Paths in a Grid with Obstacles

In this problem, you are given a grid of size (m \times n) composed of characters '.' and '#' where '.' represents a walkable cell and '#' represents an obstacle. Your task is to determine the number of unique paths from the top-left cell to the bottom-right cell. You are only allowed to move either down or right at any step, and you must avoid the cells containing obstacles. Each cell may only be visited once per path.

Note: If the starting or ending cell is an obstacle, the answer is 0.

Example: For a grid:

... 
.#. 
... 

There are 2 distinct paths from the top-left to the bottom-right.

The problem can be solved efficiently using dynamic programming where the state transition is defined as: [ \text{dp}(i,j) = \begin{cases} 0, & \text{if } grid[i][j]=='#' \ \text{dp}(i-1,j) + \text{dp}(i,j-1), & \text{otherwise} \end{cases} ] with the base case (\text{dp}(0,0)=1) (provided (grid[0][0] \neq '#')).

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains two integers (m) and (n), representing the number of rows and columns of the grid, respectively. This is followed by (m) lines, each containing a string of length (n) representing a row of the grid. Each character in the string is either a '.' (walkable cell) or a '#' (obstacle).

outputFormat

Output a single integer representing the number of unique paths from the top-left corner to the bottom-right corner of the grid. The output should be written to standard output (stdout).## sample

3 3
...
.#.
...

2