Count Paths in a Grid with Obstacles

Given a grid of size \(n \times m\), you start at the top-left cell (1,1) and need to reach the bottom-right cell (n,m). You are only allowed to move either down or right at any step.

Some cells in the grid are blocked, meaning they cannot be part of the path. You are provided with \(k\) blocked cells, each specified by its row and column indices. If the starting cell (1,1) or the ending cell (n,m) is blocked, then the answer is 0.

Your task is to compute the number of distinct paths from (1,1) to (n,m) avoiding the blocked cells. The result can be computed using dynamic programming with the recurrence:

\[ dp[i][j] = \begin{cases} 0, & \text{if cell } (i,j) \text{ is blocked},\\ dp[i-1][j] + dp[i][j-1], & \text{otherwise, with appropriate boundaries.} \end{cases} \]

Print the number of such paths.

inputFormat

The input is provided via standard input (stdin) in the following format:

1. The first line contains two space-separated integers \(n\) and \(m\) representing the number of rows and columns of the grid.
2. The second line contains a single integer \(k\) indicating the number of blocked cells.
3. The next \(k\) lines each contain two space-separated integers \(r\) and \(c\) representing the row and column indices of a blocked cell.

outputFormat

Output a single integer on standard output (stdout) representing the number of distinct paths from the top-left cell (1,1) to the bottom-right cell (n,m) that avoid the blocked cells.

3 3
0

6