HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > ProgramHER 2019 > problem:


3. Check-Mate

ProgramHER 2019

Start: Mar.03.2019 at 09:59:00 AM
Finish: Mar.03.2019 at 12:54:00 PM
The contest is finished!
• Contest scoreboard

Contest problems

• 1. Word Puzzle
• 2. Trip to Librazhd
• 3. Check-Mate
• 4. Post Office Delivery

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.
Prepared by Ibrahim Mesecan.

Check-Mate

In Checkers game, players can move each piece only diagonally (see the image).

Question:
You are given a board configuration with some unmovable pieces. Write a program that finds the distance of the shortest path from a given starting coordinate to a destination. Note: The pieces cannot jump over pieces.

Input specification
Firstly, you will be first given 2 integers

  • Board size (n) where 1 ≤ n ≤ 200 and board is an n-by-n matrix
  • The number of preoccupied cells (m) where 0 ≤ m ≤ 1000
The second line contains four integers starting and destination (x, y) positions for the piece you are moving. The next m-lines contain (x, y) coordinates of preoccupied cells.

Output specification
If the destination is not reachable, show -1. Otherwise, show minimum distance to 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