Count Distinct Maze Paths

You are given a maze represented by an n × m grid. Each cell in the maze is either empty (denoted by 0) or contains an obstacle (denoted by 1). Your task is to count the number of distinct paths from the top-left corner (cell (1, 1)) to the bottom-right corner (cell (n, m)). You may only move either right or down at any point in time.

The problem can be solved using dynamic programming. The recurrence is given in LaTeX format as follows:

$$dp_{i,j} = \begin{cases} 0 & \text{if } maze[i][j] = 1 \\ dp_{i-1,j} + dp_{i,j-1] & \text{if } maze[i][j] = 0 \end{cases}$$

Note that if the start or the end cell is blocked, the answer is 0.

inputFormat

The input is received from stdin as follows:

1. The first line contains two integers n and m, representing the number of rows and columns of the maze.
2. This is followed by n lines, each containing m integers (either 0 or 1) separated by spaces, representing the maze.

outputFormat

Output the number of distinct paths from the top-left to the bottom-right corner on a single line to stdout.

3 3
0 0 0
0 0 0
0 0 0

6