Connection Status:
Competition Arena > EscapeTheJail

EscapeTheJail

SRM 356 · 2007-07-02 · by Pawa

SRM 356 · 2007-07-02 · by Pawa · Math
Class Name: EscapeTheJail
Return Type: double
Method Name: findExit
Arg Types: (vector<string>)
Problem Statement

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.

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.

Statement by TopCoder, Inc. — view the original on the archive.

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
4)
{"@........$"}
Returns: 81.0

Submissions are judged against all 105 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EscapeTheJail with a public method double findExit(vector<string> jail) · 105 test cases · 2 s / 256 MB per case

Submitting as anonymous