Unique Paths in a Grid with Obstacles

You are given an n × n grid. The task is to determine the number of unique ways to move from the top-left cell (1,1) to the bottom-right cell (n,n), when some cells are blocked by obstacles.

You can only move either right or down at any step. If a cell contains an obstacle, you cannot travel through it. The obstacles are provided as a list of positions. Note that if the start or the end cell is blocked by an obstacle, there is no valid path.

The number of unique paths in a clear grid (without obstacles) is given by the combinatorial formula:

$$ \binom{2(n-1)}{n-1} $$

However, obstacles modify the grid dynamically and the result must be computed using dynamic programming techniques.

inputFormat

The input is read from standard input (stdin). The first two integers are n and k, where n is the size of the grid (n × n) and k is the number of obstacles. Following these, there are k pairs of integers.

Each pair of integers x y represents the position of an obstacle in the grid, where (1, 1) corresponds to the top-left corner and (n, n) corresponds to the bottom-right corner.

outputFormat

The output is a single integer printed to standard output (stdout) representing the number of unique paths from the top-left corner to the bottom-right corner that avoid all obstacles.

3 0

6