ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > CEN303 2013-15 Questions > задача:


2.15FE-03. 50996 - Checkers - the shortest path

CEN303 2013-15 Questions

Старт: 15.дек.2013 в 14:00:00
Финиш: 15.дек.2013 в 19:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (2)

Задачи турнира

• 15MdE-40. 50805 - Sum of the weig...
• 15PrE-10. 50816 - Largest Sum Path
• 15PrE-20. 50817 - The Knight Move
• 15PrE-30. 50818 - Depth Limited BST
• 15PrE-40. 50819 - Linked Numbers
• 15PrE2-01. 50847 - The first m train...
• 15PrE2-06. 50837 - Sum is equal to K
• 15Rst-10. 50857 - Nine-Stones Game
• 2.15FE-03. 50996 - Checkers - ...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 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


Для отправки решений необходимо выполнить вход.

www.contester.ru