Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by Ibrahim Mesecan.
Check-Mate
In Checkers game, players can move each piece only diagonally (see the image).
Question:
You are given a board configuration with some unmovable pieces. Write a program that finds the distance of the shortest path from a given starting coordinate to a destination. Note: The pieces cannot jump over pieces.
Input specification
Firstly, you will be first given 2 integers
- Board size (n) where 1 ≤ n ≤ 200 and board is an n-by-n matrix
- The number of preoccupied cells (m) where 0 ≤ m ≤ 1000
The second line contains four integers starting and destination (x, y) positions for the piece you are moving. The next m-lines contain (x, y) coordinates of preoccupied cells.
Output specification
If the destination is not reachable, show -1. Otherwise, show minimum distance to reach to the destination.
Sample Input I
5 5
1 1 3 5
3 1
1 3
1 2
4 4
3 2
|
Sample Input II
4 2
1 1 2 4
4 1
2 2
|
Sample Output I
4
|
Sample Output II
-1
|
Для отправки решений необходимо выполнить вход.
|