HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > "Informatics Stars" Online Contests - 2011-2014 > problem:


50779 - The shortest path in a maze

"Informatics Stars" Online Contests - 2011-2014

Start: Oct.20.2012 at 10:00:00 AM
Finish: Oct.20.2012 at 03:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (2)

Contest problems

• 50326 - Matrix Operations
• 50325 - How much time passed?
• 50776 - The number of different pa...
• 50779 - The shortest path in a ...
• 2011-04-1. 50586 - Prime Palindromes
• 2011-04-2. 50585 - Inner Product
• 2011-04-3. 50587 - Modular Convers...
• 2011-05-1. 50767 - Censor
• 2011-05-2. 50652 - Prime Factorization
• 2011-05-3. 50653 - Long Divide
• 2011-11-1. 50565 - Binary numbers
• 2011-11-3. 50588 - Processing the li...

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.

The shortest path in a maze

Shqip

Your friend has stuck in a maze. There can be several different paths but he whants to find the length of the shortest path.
There are four directions that he can move on: east, west, south and north (he cannot move diagonally).

Input specification
At the first line, there is a number (N) which shows the size of the square matrix where 2 ≤ N ≤ 20.
Then, you will be given NxN matrix composed of the following numbers:
    '0' ==> an empty cell in which he can pass through.
    '-1' ==> an obstacle (or a wall)
    '1' ==> the starting position of your friend
    '-2' ==> the destination that your friends has to reach

Output specification
Show just one number that shows the length of the shortest path reaching to the destination.
If the destination is not reachable, print -1, meaning that there is no path.

Sample Input I:                 Sample Output I:
    4                 4
    0  0  0  0
    1 -1 -1  0
    0  0 -2  0
   -1  0  0 -1

Sample Output I - Explanation:
    4
    0  0  0  0
    1 -1 -1  0
    2  3  4  0
   -1  0  0 -1

Sample Input II:                 Sample Output II:
    3                 5
    1 0 -1
   -1 0 0
   -2 0 0




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

www.contester.ru