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

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


15PrE-20. 50817 - The Knight Move

CEN303 2013-15 Questions

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

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

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

• 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...
• 15MdE-40. 50805 - Sum of the weig...
• 15PrE-10. 50816 - Largest Sum Path
• 15PrE-20. 50817 - The Knight M...
• 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 - the ...

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

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

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

The Knight Move

In chess the knight has 8 possible moves. Assume that you are given only 4 possible moves for it: for a position (x, y) the possible moves are (x+2, y+1), (x+1, y-2), (x-1, y+2) and (x-2, y-1) (refer the image on the right for orientation). And assume that this is not a chessboard but an n x n board. If you are given the initial (xi, yi) and final (xf, yf) positions of it, 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 if the knight can move over the destination (xf, yf) cell or not.

Input specification
You will be first given 2 numbers

  • The size of the board (n) where the board is an nxn matrice and 1 ≤ n ≤ 100
  • The number of cells (m) occupied by other pieces where 0 ≤ m ≤ 500
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 "Yes", if there is a possible path to the destination. "No", otherwise.

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  
No
Sample Output II
Yes


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

www.contester.ru