Unique Paths in a Maze

Given a maze represented by an N x M grid, where each cell can either be free (denoted by 0) or blocked (denoted by 1), determine the number of unique paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (N,M)). You can only move either down or right at any point in time.

The problem can be formalized using dynamic programming. Let \( dp[i][j] \) be the number of paths from the start to cell \( (i, j) \). The recurrence is given by :

\( dp[i][j] = \begin{cases} 0, & \text{if } Maze[i][j] = 1 \text{ (an obstacle)} \\ dp[i-1][j] + dp[i][j-1], & \text{otherwise} \end{cases} \)

If the starting or ending cell is blocked, the answer is 0.

inputFormat

The first line of input contains two integers N and M (1 ≤ N, M ≤ 1000), the number of rows and columns in the maze respectively. The following N lines each contain M integers (either 0 or 1) separated by spaces, representing the maze.

outputFormat

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

2 2
0 0
1 0

1