Grid Paths with Obstacles

Given an H \(\times\) W grid where each cell is either free (represented by '.') or blocked (represented by '#'), your task is to determine the number of distinct paths from the top-left corner to the bottom-right corner. You can only move either right or down.

A valid path must not pass through any blocked cells and both the starting cell and the destination cell must be free. The number of ways can be computed using dynamic programming with the recurrence:

\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)

with suitable base conditions.

inputFormat

The first line contains two integers H and W separated by a space. The next H lines each contain a string of length W composed of the characters '.' and '#' where '.' indicates a free cell and '#' indicates an obstacle.

outputFormat

Output a single integer representing the number of valid paths from the top-left corner to the bottom-right corner.## sample

3 3
...
.#.
...

2