EscapeTheJail
SRM 356 · 2007-07-02 · by Pawa
SRM 356 · 2007-07-02 · by Pawa · Math
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
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
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