Unique Paths in a Grid with Obstacles

You are given an n x m grid where some cells are blocked. Starting from the top-left cell (1,1), your goal is to reach the bottom-right cell (n,m) by moving only right or down. The challenge is to count the number of unique paths from the start to the end while avoiding the blocked cells.

If a cell is blocked, you cannot pass through it. The recurrence relation used in dynamic programming is given by:

\( dp[i][j] = dp[i-1][j] + dp[i][j-1] \)

if cell \((i,j)\) is not blocked, otherwise \(dp[i][j] = 0\). Note that the grid and the blocked cell positions are 1-indexed.

inputFormat

The first line of the input contains three integers: n (the number of rows), m (the number of columns), and k (the number of blocked cells). This is followed by 2*k integers, representing k pairs. Each pair contains two integers representing the row and column indices of a blocked cell. All input is provided via stdin.

outputFormat

Output a single integer, which is the number of unique paths from the top-left corner to the bottom-right corner avoiding the blocked cells. The answer should be printed to stdout.

3 3 0

6