Shortest Path with Obstacles

You are given an \(m \times n\) grid. The starting cell is \((0,0)\) and the target cell is \((x,y)\). Some cells in the grid contain obstacles which cannot be passed. You can move only in four directions: up, down, left, and right. Your task is to determine the length of the shortest path from the starting cell to the target cell while avoiding obstacles. If there is no valid path, output \(-1\).

Note: The coordinates of obstacles and cells are 0-indexed.

inputFormat

The input is read from standard input (stdin) and consists of the following lines:

• The first line contains four integers \(m\), \(n\), \(x\), and \(y\), where \(m\) and \(n\) denote the dimensions of the grid, and \(x\) and \(y\) denote the target cell's coordinates.
• The second line contains an integer \(k\) representing the number of obstacles.
• The next \(k\) lines each contain two integers representing the coordinates of an obstacle.

It is guaranteed that all coordinates satisfy \(0 \leq row < m\) and \(0 \leq col < n\).

outputFormat

Output a single integer to standard output (stdout) which is the length of the shortest path from \((0,0)\) to \((x,y)\). If there is no valid path, output \(-1\).

3 3 2 2
2
0 1
1 1

4