Unique Paths in a Maze

Given an m x n grid representing a maze, where each cell is either open (.) or blocked (#), your task is to compute the number of unique paths from the top-left corner to the bottom-right corner. You can only move either right or down at any step.

A valid path must start at the top-left cell and end at the bottom-right cell. If either the starting or ending cell is blocked, the answer is 0.

The solution employs dynamic programming with the following recurrence relation in latex format:

$$ \text{dp}(i,j)=\begin{cases} 0, & \text{if } grid[i][j]=\#, \\ \text{dp}(i-1,j)+\text{dp}(i,j-1), & \text{if } grid[i][j]=. \end{cases} $$

inputFormat

The input is provided via stdin and has the following format:

• The first line contains two integers, m and n, the number of rows and columns respectively.
• Each of the following m lines contains a string of length n where each character is either . (open) or # (blocked).

outputFormat

Output a single integer to stdout — the number of unique paths from the top-left corner to the bottom-right corner.

3 3
...
.#.
...

2