Queen
On a generalized chessboard (not necessarily 8×8), a queen is placed. You know the square where it currently resides and the square it needs to reach. The challenge is that some squares are occupied by enemy pieces. However, these pieces are fast asleep, allowing the queen to move quietly as many times as needed. The queen cannot jump over or capture these enemy pieces, as doing so would wake them up.
Your task is to write a program that determines the minimum number of moves the queen needs to make to reach the target square.
Input
The program reads from the keyboard the dimensions of the chessboard: first, the number of verticals w (2 ≤ w ≤ 26), then the number of horizontals h (2 ≤ h ≤ 99). Next, it reads the coordinates of the starting and ending squares, followed by the number of enemy pieces K (0 ≤ K ≤ w·h–2). After that, K pairs of numbers are provided, representing the coordinates of each enemy piece. All numbers are separated by spaces. The coordinates of all squares are natural numbers not exceeding w and h, respectively. The vertical coordinate is given first, followed by the horizontal. The starting and ending squares do not contain enemy pieces, and no two enemy pieces occupy the same square.
Output
The program should output a single integer: the minimum number of moves required for the queen to travel from the starting square to the ending square, or -1 if it is impossible to reach the destination.