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
Для отправки решений необходимо выполнить вход.
|