Count Paths in a Grid With Obstacles

You are given a rectangular grid with R rows and C columns. Each cell in the grid is either an empty cell denoted by a dot ('.') or an obstacle denoted by a hash ('#'). Your task is to compute the number of distinct paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (R,C)), where you can only move either right or down at any step.

The dynamic programming recurrence used to count the paths is given by

for any cell (i, j) that does not contain an obstacle, with the appropriate boundary conditions. If either the starting cell or the destination cell is blocked (i.e. contains '#'), the answer is 0.

This problem requires efficient handling of grid based dynamics and careful consideration of obstacles.

inputFormat

The first line contains two space-separated integers $R$ and $C$, the number of rows and columns respectively. This is followed by $R$ lines, each containing a string of length $C$ that represents a row of the grid. Each character in the string is either '.' (an empty cell) or '#' (an obstacle).

outputFormat

Output a single integer representing the number of distinct paths from the top-left corner to the bottom-right corner of the grid that avoid obstacles, using only rightward and downward moves.## sample

1 1
.

1