Statistics

Problem Statement for "BadMazeStrategy"

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.

Definition

Class:
BadMazeStrategy
Method:
numSteps
Parameters:
String[]
Returns:
int
Method signature:
int numSteps(String[] maze)
(be sure your method is public)

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

Examples

  1. {"XXXXXXX" ,"X.....X" ,"X.....X" ,"XY...DX" ,"X.....X" ,"XXXXXXX"}

    Returns: 4

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

  2. {"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.

  3. {"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.

  4. {"DY............."}

    Returns: 27

    Don't run off the maze.

  5. {"Y..X.............." ,"XXX.XXXXXXXXXXXX.X" ,".X.X.XX.......D..." ,".XX.XXX..........."}

    Returns: 39

  6. {".........................D" ,"X........................." ,".XXXXXXXXXXXXXXXXXXXXXXXXX" ,"Y........................."}

    Returns: 76

  7. {"..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" ,"..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" ,"..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" ,"..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" ,"..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" ,"..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" ,"..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" ,"..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" ,".XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" ,".................................................." ,"DXY.............................................XX" }

    Returns: -1

  8. {"Y.................................XD"}

    Returns: -1

  9. {".................................................." ,".D................................................" ,".X................................................" ,"................................................XX" ,"Y................................................." ,".................................................."}

    Returns: 203

  10. {".................................................D" ,"Y................................................."}

    Returns: 148

  11. {".................................................." ,"..XX.............................................." ,"................................................X." ,"...XD...........................................X." ,"...X.............................................." ,".X............................................XX.." ,".X................................................" ,"................................................XX" ,"Y................................................." ,".................................................."}

    Returns: 305

  12. {"Y................................................." ,"D................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." }

    Returns: 195

  13. {"D" ,"Y" ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"." ,"."}

    Returns: 97

  14. {"YX................................................" ,"..D..............................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." }

    Returns: -1

  15. {"YX................................................" ,"X................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................D" ,".................................................." }

    Returns: 242

  16. {"YX................................................" ,"X................................................." ,".................................................." ,"..D..............................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".................................................." ,".X................................................" ,".X................................................" ,"................................................XX" ,".................................................." }

    Returns: 330

  17. {"YD"}

    Returns: 1

  18. {"DY"}

    Returns: 1

  19. {"DXY" ,"XXX"}

    Returns: -1

  20. {"DX" ,"XY"}

    Returns: 1

  21. {"Y........XXXX" ,"XXXXXXXXX.XXX" ,"XXXXXXXXXX.XX" ,"XXXXXXXXXXX.X" ,"XXXXXXXXXXXX." ,"XXXXXXXXXXXX." ,"XXXXXXXXXXXX." ,"XXXXXXXXXXXX." ,"XXXXXXXXXXX.X" ,"XXXXXXXXXXXDX"}

    Returns: -1

  22. {"Y........XXXX" ,"XXXXXXXXX.XXX" ,"XXXXXXXXXX.XX" ,"........XXX.X" ,".XXXXXXX.XXX." ,".XX...XX.XXX." ,".XX.XXDX.XXX." ,".XXX.....XXX." ,".XXXXXXXXXX.X" ,"X..........XX"}

    Returns: 52

  23. { "XXXXXXX", "XY....X", "X.....X", "X.....X", "X....DX", "XXXXXXX" }

    Returns: 7

  24. { "DY............." }

    Returns: 27

  25. { "YXD" }

    Returns: -1

  26. { "DXY" }

    Returns: -1

  27. { "XXXD", "XYX.", "XXX." }

    Returns: -1

  28. { "XXXX", "XYXX", "XXXX", "...D" }

    Returns: -1

  29. { "Y.................................................", "D................................................." }

    Returns: 99

  30. { "XXY...XXDX" }

    Returns: -1

  31. { "XXXXXXX", "X.....X", "X.Y...X", "X..D..X", "X.....X", "XXXXXXX" }

    Returns: -1

  32. { "XXX", "YXD", "XXX" }

    Returns: -1

  33. { "YX.", "XXX", ".XD" }

    Returns: -1

  34. { "DY....X", "XXXX..X" }

    Returns: -1

  35. { "XXXXXXX", "XY....X", "X.....X", "X..D..X", "X.....X", "XXXXXXX" }

    Returns: -1

  36. { "XXX", "XDX", "XXX", "XYX", "XXX" }

    Returns: -1

  37. { "XXX", "XYX", "XXX", "XDX" }

    Returns: -1

  38. { "XXXXX", "XYXDX", "XXXXX" }

    Returns: -1

  39. { "XYXDX" }

    Returns: -1

  40. { "Y..X..............", "XXX.XXXXXXXXXXXX.X", ".X.X.XX.......D...", ".XX.XXX..........." }

    Returns: 39

  41. { "DY...", "XXXX.", "X....", "X....", "XXXXX" }

    Returns: -1

  42. { "Y...", "DX.." }

    Returns: -1

  43. { ".Y.", ".D.", "..." }

    Returns: -1

  44. { "XXXXXX", "X....X", "X.DY.X", "X....X", "XXXXXX" }

    Returns: -1

  45. { "XXXXXXX", "X.....X", "X.X.X.X", "X..Y..X", "X.D.X.X", "X.....X", "XXXXXXX" }

    Returns: -1

  46. { "XXXXXX", "X....X", "X.Y..X", "X..D.X", "X....X", "XXXXXX" }

    Returns: -1

  47. { "YXD", "XXX" }

    Returns: -1

  48. { "XXXXXXX", "X.....X", "X..D..X", "XY....X", "X.....X", "XXXXXXX" }

    Returns: -1

  49. { "DY..", "XX..", "XX.." }

    Returns: -1

  50. { "D", "X", "Y" }

    Returns: -1

  51. { "X..X.", "Y..XD", "X..X.", "X..X." }

    Returns: -1

  52. { "YXXX", "XXDX" }

    Returns: -1

  53. { ".............", ".............", "........D....", "......X.....X", ".......X.....", ".............", "..Y..........", "...........XX", "X............", ".......X.....", ".......X....." }

    Returns: 79

  54. { "D...Y" }

    Returns: 4

  55. { "Y..", "DX." }

    Returns: -1

  56. { "XXXD", "XYX.", "XXXX" }

    Returns: -1

  57. { "YXX", "XDX", "XXX" }

    Returns: 1

  58. { "XXX.D", "XYX..", "XXX.." }

    Returns: -1

  59. { "....", ".DY.", "...." }

    Returns: -1

  60. { "XXXXXX", "XY.XDX", "XXXXXX" }

    Returns: -1

  61. { "XXXXX", "DY..X", "XXX.X", "X...X", "XXXXX" }

    Returns: -1

  62. { "XXXXXXX", "X.....X", "XXXD..X", "XYX...X", "XXX...X", "XXXXXXX" }

    Returns: -1

  63. { "XXXXX", "XYXXX", "XXXDX", "XXXXX" }

    Returns: -1

  64. { "Y.................................................", "XX................................................", "................................................X.", "..XX............................................X.", "..............................................X...", "....XX........................................X...", "............................................X.....", "......XX....................................X.....", "..........................................X.......", "........XX................................X.......", "........................................X.........", "..........XX............................X.........", "......................................X...........", "............XX........................X...........", "....................................X.............", "..............XX....................X.............", "..................................X...............", "................XX................X...............", "................................X.................", "..................XX............X.................", "..............................X...................", "....................XX........X...................", "............................X.....................", "......................XX....X.....................", "..........................X.......................", "..........................X.......................", ".....................X............................", ".....................X............................", "...................X......XX......................", "...................X..............................", ".................X..........XX....................", ".................X................................", "...............X..............XX..................", "...............X..................................", ".............X..................XX................", ".............XD...................................", "...........X......................XX..............", "...........X......................................", ".........X..........................XX............", ".........X........................................", ".......X..............................XX..........", ".......X..........................................", ".....X..................................XX........", ".....X............................................", "...X......................................XX......", "...X..............................................", ".X..........................................XX....", ".X................................................", "..............................................XX..", ".................................................." }

    Returns: 1099

  65. { "XXXXXXX", "XYX...X", "XXX...X", "X.....X", "X....DX", "XXXXXXX" }

    Returns: -1

  66. { "Y", ".", ".", ".", ".", ".", ".", ".", ".", "D" }

    Returns: 9

  67. { "DY................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", "..................................................", ".................................................." }

    Returns: 195

  68. { "XYX", ".D.", "X.X" }

    Returns: -1

  69. { "XD", "YX" }

    Returns: 1

  70. { "XXXXXX", "XYXXXX", "XXXXXX", "XDXXXX", "XXXXXX" }

    Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: