TopCoder problem "EscapeTheJail" used in SRM 356 (Division I Level Three)



Problem Statement

    You are a prisoner and you want to escape from your jail. The jail is a grid where each square is either free or impassible. There are one or more exits located in free squares. You are initially standing in a free square and your goal is to reach one of the exits. Unfortunately, your eyes are covered, so you cannot see where you're going. Each time you move, you check up, down, left and right to see which of those four adjacent squares are free, and you randomly walk to one of the free squares. You continue to do this until you land on a square containing an exit. If there is no adjacent free cell, you stay at your current position.

You are given a String[] jail, where your start location is marked by the '@' character, impassible squares are marked with '#', exits are marked with '$' and all other free squares are '.'. Return a double representing the expected number of moves required to escape. If it is impossible to escape, return -1.
 

Definition

    
Class:EscapeTheJail
Method:findExit
Parameters:String[]
Returns:double
Method signature:double findExit(String[] jail)
(be sure your method is public)
    
 

Constraints

-jail will contain between 1 and 15 elements, inclusive.
-Each element of jail will contain between 1 and 15 characters, inclusive.
-All elements in jail will contain the same number of characters.
-Each character in each element of jail will be '.', '#', '$' or '@'.
-jail will contain exactly one '@' character.
-jail will contain at least one '$' character.
 

Examples

0)
    
{"@$"}
Returns: 1.0
You have only one possible move, and it leads you to the exit. So, the answer is 1.
1)
    
{"$.",
 ".@"}
Returns: 4.0
2)
    
{"@..$"}
Returns: 9.0
3)
    
{"@#",
 "#$"}
Returns: -1.0

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7353

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10765&pm=7353

Writer:

Pawa

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Math