Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by Ibrahim Mesecan.
The number of different paths in a maze
Shqip
Your friend has stuck in a maze. There are several different paths but he cannot find any. You want to show that
that actually there are several different paths. At the end, you count the number of different paths and show him.
There are four directions that he can move on: east, west, south and north (he cannot move diagonally).
Write a program that is going to find the number of different paths reaching to the destination.
Input specification
There is a number (N) first 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 number of different paths reaching to the destination.
Otherwise, print 0 (zero), meaning that there is no path.
Note: The number of different paths are at most 10.000
Sample Input I: Sample Output I:
3 2
1 0 -1
-1 0 0
-2 0 0
Explanation of the Output I : There are 2 different paths. Here are they
Path 1 Path 2
1 2 -1 1 2 -1
-1 3 0 -1 3 4
-2 4 0 -2 6 5
Sample Input II: Sample Output II:
4 3
0 0 0 0
1 -1 -1 0
0 0 -2 0
-1 0 0 -1
Sample Input III:
6
1 0 0 0 0 0
0 0 0 0 0 0
-1 -1 -1 -1 0 0
0 0 0 -1 0 0
0 0 0 -1 0 0
0 0 0 -1 0 -2
Sample Output III:
448
Для отправки решений необходимо выполнить вход.
|