|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Prepared by Ibrahim Mesecan.
Checkers - the shortest path
Checkers is a board game, in which the pieces
can move only in diagonals. Refer to the image
for orientation and possible moves.
Question:
Write a program that finds the fastest move
from a given (xf, yf) coordinate
to the destination. Note:
Assume that your pieces cannot jump over the given
obstacles.
Input specification
Firstly, you will be first given 2 integers
- The size of the board (n) where the board is
an nxn matrix and 1 ≤ n ≤ 250
- The number of cells (m) occupied by other pieces
where 0 ≤ m ≤ 5000
Then in the following line you will be given four
integers initial (xi, yi) starting
position and the destination (xf, yf).
Then, in the
following m lines you will be given (x,y) coordinates
of m occupied cells.
Output specification
Show the minimum number of moves that the pieces can
reach to the destination. Show -1, if it
cannot 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
|
Для отправки решений необходимо выполнить вход.
|