HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


51072 - Castle on chessboard

Guest
• Review clarifications (1)

Section problems

• 50675 - Kruja Boys
• 50679 - Jetpack Hurdle Jumping
• 50673 - DNA Testing
• 50997 - Dynamic Knights
• 50936 - Saving the Soldiers
• 50979 - Minimum access cost for BST
• 51062 - Fish Pond II
• 51010 - Max Sequential Sum
• 51072 - Castle on chessboard
• 51075 - Shortest Path for Bishop
• 50688 - Epoka Furgon
• 50524 - Elevator
• 50536 - Epoka Furgon Shpk
• 50687 - Pascal Triangle - 2
• 50689 - The biggest building block
• 50686 - The Container
• 50682 - Hotel Durres

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

Castle on chessboard

Question: You have some pieces (blocked cells) on a chessboard and a castle. Show at least in have many moves the castle can move to the given destination.

Input specification: You will be first given 4 integers (x,y) coordinates of starting and destination cells. Then you will be given an integer (n) the number of blocked cells. Each of the following n lines will provide two integers (x,y) coordinates of the blocked cells.

Output specification: Show one integer, the length of shortest path. Show -1, if there is no path.

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



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

www.contester.ru