Counting Grid Paths with Obstacles

In this problem, you are given an (m \times n) grid where some cells may be blocked. Your task is to determine the number of distinct paths from the top-left corner (cell (0,0)) to the bottom-right corner (cell (m-1, n-1)). You can only move either right or down at any step. If the starting cell or the destination cell is blocked, the answer is (0).

A common approach is to use Dynamic Programming with the following recurrence: [ dp[i][j] = dp[i-1][j] + dp[i][j-1] ]

where (dp[i][j]) represents the number of ways to reach cell ((i,j)). Make sure to consider cells that are blocked appropriately by setting their (dp) value to (0).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers, (m) and (n), representing the number of rows and columns in the grid respectively.
• The second line contains an integer (k), representing the number of blocked cells.
• The following (k) lines each contain two integers, representing the row and column indices of a blocked cell (0-indexed).

For example:

3 3 1 1 1

represents a 3x3 grid with one blocked cell at position ((1,1)).

outputFormat

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

3 3
0

6