Grid Shortest Path with Walls

You are given a 2D grid of size \(M \times N\) where some cells contain walls. Your task is to determine the minimum number of moves required to travel from a given starting cell to a destination cell, moving only up, down, left, or right. If the destination is unreachable, output \(-1\).

The grid is represented by its number of rows (M) and columns (N). The positions of the walls are provided as coordinates. After listing all wall positions, the starting coordinates and destination coordinates are given. Multiple test cases can be specified; the input terminates with a line containing 0 0 0.

Note: Use a breadth-first search (BFS) to find the shortest path in the grid. Ensure that your solution reads from standard input (stdin) and writes to standard output (stdout).

inputFormat

The input consists of multiple test cases. Each test case starts with a line containing three integers \(M\), \(N\), and \(K\) where \(M\) and \(N\) are the grid dimensions and \(K\) is the number of wall cells. The next \(K\) lines each contain two integers representing the row and column indices of a wall.

Following the wall positions, there are two lines: the first contains the starting cell coordinates (row and column) and the second contains the destination cell coordinates. The input concludes with a line containing "0 0 0", which should not be processed.

outputFormat

For each test case, output a single integer on a new line: the minimum number of moves required to reach the destination from the start, or \(-1\) if it is impossible to reach the destination.

## sample

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

8
-1

</p>