Connection Status:
Competition Arena > BadMazeStrategy

BadMazeStrategy

TCO04 Round 1 · 2004-09-07 · by AdminBrett

TCO04 Round 1 · 2004-09-07 · by AdminBrett · Simulation
Class Name: BadMazeStrategy
Return Type: int
Method Name: numSteps
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You will be given a String[] maze containing blank spots ('.' characters), walls ('X' characters), your character (a single 'Y' character), and the destination (a single 'D' character). You have implemented the following naive maze traversal strategy:
  • 1) Initially, set the current direction to Right.
  • 2) If you are on the destination spot, exit this process.
  • 3a) If taking 1 step in the current direction will lead to a blank spot or the destination take the step.
  • 3b) If taking 1 step in the current direction will lead to a wall or will leave the bounds of the maze, change the current direction by turning 45 degrees clockwise. For example, if the current direction is set to Right then turning 45 degrees clockwise will set the current direction to Down-Right.
  • 4) Go to step 2.
Character 0 is the leftmost spot in any element of maze. Furthermore, element 0 is the highest element of maze. Return the number of steps required to reach the destination, or -1 if this will never occur. A step is counted when you physically change spots but not when you simply change direction.

Notes

  • If your character is at (element E, character C) of maze, and the current direction is Down-Right, then taking one step would leave you at (element E+1, character C+1) of maze. The other diagonal directions are treated analogously.
  • The following sequence of directions are formed by consecutively turning 45 degrees clockwise:Right, Down-Right, Down, Down-Left, Left, Up-Left, Up, Up-Right, Right.

Constraints

  • maze will contain between 1 and 50 elements inclusive.
  • Each element of maze will contain between 1 and 50 characters inclusive.
  • Each element of maze will contain the same number of characters.
  • Each character in maze will be (quotes for clarity) '.', 'X', 'Y', or 'D'.
  • maze will contain exactly one 'Y' and one 'D'.

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

Examples
0)
{"XXXXXXX"
,"X.....X"
,"X.....X"
,"XY...DX"
,"X.....X"
,"XXXXXXX"}
Returns: 4

After taking 4 steps to the right, we reach the destination.

1)
{"XXXXXXX"
,"XY....X"
,"X.....X"
,"X.....X"
,"X....DX"
,"XXXXXXX"}
Returns: 7

After taking 4 steps to the right, continuing would lead into a wall. After changing direction to Down-Right we are still facing a wall, so we change directions again. Now facing downward we take 3 more steps and reach the destination.

2)
{"XXXXXXX"
,"XY....X"
,"X.....X"
,"X..D..X"
,"X.....X"
,"XXXXXXX"}
Returns: -1

We keep running around the perimeter while the destination lies in the center.

3)
{"DY............."}
Returns: 27

Don't run off the maze.

4)
{"Y..X.............."
,"XXX.XXXXXXXXXXXX.X"
,".X.X.XX.......D..."
,".XX.XXX..........."}
Returns: 39

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

Coding Area

Language: C++17 · define a public class BadMazeStrategy with a public method int numSteps(vector<string> maze) · 70 test cases · 2 s / 256 MB per case

Submitting as anonymous