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

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


15FE-04. 50997 - Dynamic Knights

CEN303 2013-15 Questions

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

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

• 14-Fall2-20. 50794 - Writing Files Int...
• 14-Fall2-30. 50490 - Across the River
• 14-Fall2-40. 50772 - The Path of a N...
• 14-Fall2-50. 50681 - Center of a Series
• 14-FallResit-10. 50525 - Ordering Pizza
• 14-FallResit-20. 50488 - Connecting...
• 15FE-01. 50851 - Repeated Numbers
• 15FE-01. 50838 - Balanced Numbers
• 15FE-04. 50997 - Dynamic Knights
• 15HW-10. 50826 - Olive Containers
• 15HW-30. 50828 - Arranging Time ...
• 15HW-40. 50676 - Cinema Millennium
• 15HW-40. 50829 - Decode an Image
• 15HW-50. 50830 - Sorting BST Nodes
• 15HW-60. 50678 - The Jumping Rabbit
• 15MdE-10. 50802 - Comparing Exams
• 15MdE-20. 50803 - Sum of the dept...

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

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

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Question by Ibrahim Mesecan.

Dynamic Knights

Your knights had limitations therefore they could fight in a smaller area. Now, they have taken algorithms course and they are dynamic knights who can fight in a wider area: 400 x 400 board. See the image for orientation and possible moves. If you are given the initial (xi, yi) and the final (xf, yf) coordinates, and if you are also given m positions which are occupied by other pieces where the knight cannot move on them.

Question:
Write a program that tries all possible moves and decides the fastest move where the knight can move over the destination (xf, yf) cell.

Input specification
Firstly, you will be first given 2 integers

  • The size of the board (n) where the board is an nxn matrice and 1 ≤ n ≤ 400
  • 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 position of the knight and the position that the knight wants to reach (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 knight can reach to the destination. Show -1, if the knight cannot reach to the destionation.

Sample Input I
3 1
1 1 2 2
1 2
Sample Input II
4 2
1 1 2 4
4 1
4 2
Sample Output I  
-1
Sample Output II
2


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

www.contester.ru