Path Counting in a Grid with Obstacles

Alice is visiting a park represented by an n×m grid. Each cell in the grid is either passable (denoted by '0') or impassable (denoted by '1'). Starting at the top‐left corner (cell (1,1)) and aiming to reach the bottom‐right corner (cell (n,m)), Alice can only move either to the right or down. Your task is to compute the number of distinct paths she can take, avoiding all impassable cells.

A dynamic programming approach can be applied, using the following recurrence formula:

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

Note that if either the starting cell or the destination cell is impassable, the answer should be 0.

inputFormat

The input is given via standard input. The first line contains two integers n and m (the number of rows and columns, respectively). This is followed by n lines, each containing a string of m characters where each character is either '0' or '1'.

outputFormat

Output a single integer which is the number of distinct paths from the top-left corner to the bottom-right corner of the grid.## sample

3 3
000
010
000

2