Unique Paths in a Grid

You are given an n x m grid, where each cell is either 1 (an open cell) or 0 (a blocked cell). Your task is to determine the number of unique paths from the top-left cell (at position (1,1)) to the bottom-right cell (at position (n,m)), such that you can only move either right or down at each step and can only travel on open cells.

The dynamic programming recurrence for the problem is given by:

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

If either the starting cell or the destination cell is blocked, no valid path exists.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains two space-separated integers n and m, the dimensions of the grid.
2. The following n lines each contain m space-separated integers (either 0 or 1) representing the grid.

outputFormat

Output a single integer via standard output (stdout) which is the number of unique paths from the top-left corner to the bottom-right corner of the grid.

3 3
1 1 1
1 0 1
1 1 1

2