Shortest Path in a Grid with Obstacles

You are given a grid of size \( m \times n \) where \( m \) is the number of rows and \( n \) is the number of columns. Some cells in the grid contain obstacles, and the grid is 1-indexed. Your task is to determine the shortest path length between given start and end points for multiple tasks, while avoiding obstacles. You can move in four directions: up, down, left, and right. Diagonal moves are not allowed.

For each task, if there exists a valid path, output the minimum number of moves required; otherwise, output \( -1 \). Note that if the start and end positions are the same and are not blocked by an obstacle, the answer is \( 0 \).

Hint: Consider using a Breadth-First Search (BFS) algorithm to traverse the grid.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains two integers \( m \) and \( n \): the number of rows and columns in the grid.
• The second line contains an integer \( o \), the number of obstacle cells.
• The next \( o \) lines each contain two integers \( x \) and \( y \) representing the 1-indexed coordinates of an obstacle.
• The following line contains an integer \( t \), the number of tasks.
• The next \( t \) lines each contain four integers \( sx \), \( sy \), \( ex \), and \( ey \) representing the starting and ending coordinates for each task.

outputFormat

For each task, output one line to standard output (stdout) with a single integer: the length of the shortest path from the start to the end point. If no path exists, output \( -1 \).

5 5
3
2 2
3 3
4 4
2
1 1 5 5
2 2 5 5

8
-1