Count Paths on Grid with Obstacles

In this problem, you are given a grid of size \(n \times m\) consisting of characters . and #. The . represents an empty cell, and # represents an obstacle. You can only move either to the right or down from any cell. Your task is to determine the number of distinct paths from the top-left cell to the bottom-right cell such that you never step on an obstacle.

If either the starting cell or the ending cell is an obstacle, there is no valid path. The recurrence relation for solving this problem using dynamic programming is given by:

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

with the initial condition \(\text{dp}[0][0] = 1\) (provided it is not blocked). Implement a program that reads the grid from standard input and outputs the number of valid paths to standard output.

inputFormat

The input is given via standard input in the following format:

n m
row1
row2
...
rown

Here, n and m are integers denoting the number of rows and columns of the grid respectively, and each of the following n lines contains a string of m characters (each either . or #) representing the grid.

outputFormat

Output a single integer on standard output — the number of valid paths from the top-left to the bottom-right corner of the grid.

3 3
.#.
...
#..

2