Counting Unique Safe Paths

You are given a grid of size n × m where each cell is either safe (0) or contains a trap (1). Your task is to compute the number of unique safe paths from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,m)). In each step you can only move either right or down.

A cell with a trap (value 1) cannot be used as part of any path. If either the starting cell or the ending cell has a trap, the answer is 0.

The recurrence relation used in the dynamic programming solution is given in LaTeX format as:

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

Here, \(dp[i][j]\) represents the number of ways to reach cell \((i,j)\) and the final answer is \(dp[n-1][m-1]\).

inputFormat

The input is read from standard input (stdin). The first line contains two integers n and m representing the number of rows and columns respectively. This is followed by n lines, each containing m integers (0 or 1) separated by spaces representing the grid.

outputFormat

Output a single integer to standard output (stdout) representing the number of unique safe paths from the top-left to the bottom-right corner of the grid.## sample

2 2
0 0
1 0

1