HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

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


50776 - The number of different paths 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 (1)

Contest problems

• 50326 - Matrix Operations
• 50325 - How much time passed?
• 50776 - The number of different...
• 50779 - The shortest path in a maze
• 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

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 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


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

www.contester.ru