HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Linear Data structures: Stacks, Queues, Linked Lists, etc > problem:


50779 - The shortest path in a maze

Guest
• Review clarifications (2)

Section problems

• 51086 - Top popular student
• 50774 - Hot Potato
• 50777 - Dwarfs Maze
• 50781 - ReversesreveR
• 50780 - Hot Potato - Revisited
• 50564 - Mother's Milk Buckets
• 50636 - Brackets
• 50776 - The number of different pa...
• 50779 - The shortest path in a ...

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