Minimum Moves in an Asteroid Field

You are given a grid of dimensions \(N \times M\) representing a segment of space. In this grid, some cells contain asteroids. Your spaceship starts at the cell (sx, sy) and needs to reach the destination (dx, dy). The spaceship can move in four directions: up, down, left, and right.

Each move increases the distance by 1. The spaceship cannot move into a cell occupied by an asteroid. Determine the minimum number of moves required to reach the destination from the starting point, or output -1 if it is impossible.

Input Format: The input is given via standard input.

Note: All coordinates are 0-indexed.

inputFormat

The input consists of several lines:

• The first line contains two integers \(N\) and \(M\), the number of rows and columns of the grid.
• The second line contains two integers \(sx\) and \(sy\), the starting coordinates.
• The third line contains two integers \(dx\) and \(dy\), the destination coordinates.
• The fourth line contains an integer \(K\), the number of asteroids.
• The next \(K\) lines each contain two integers representing the coordinates of an asteroid.

outputFormat

Output a single integer representing the minimum number of moves needed to reach the destination, or -1 if it is not possible.

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

8