Statistics

Problem Statement for "EscapeTheJail"

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

  1. {"@$"}

    Returns: 1.0

    You have only one possible move, and it leads you to the exit. So, the answer is 1.

  2. {"$.", ".@"}

    Returns: 4.0

  3. {"@..$"}

    Returns: 9.0

  4. {"@#", "#$"}

    Returns: -1.0

  5. {"@........$"}

    Returns: 81.0

  6. {"..$....","....#..",".#.##$.",".....#.","..#..#.",".#.....","....@..",".###..."}

    Returns: 130.8334268728003

  7. {"..$....","....#..",".#.##$.",".....#.","..#..#.",".#.....","....@.."}

    Returns: 109.11017808318881

  8. {".#...#.","....###",".$.....","..#.##.","#.$@#.#","....##."}

    Returns: 9.544569041717937

  9. {"#...#","...#.",".....",".$##.",".$..@","...##"}

    Returns: 25.75234317520232

  10. {".....#.","##.####","#...#..","####..#",".....##",".....#@","#.##.$."}

    Returns: 4.0

  11. {".....#.","##.####","#...#..","####..#",".....##",".....#@","#.##.$."}

    Returns: 4.0

  12. {"$.#.......","..$..##.#.","......#@.#","..#.$##...",".###.###.#","..##..##.#","#.#...#..."}

    Returns: 200.0684584980229

  13. {"##.#...#..","....##....","#.#...##.#","#.#..##.##",".####.#.##","...#...#..",".#.#......","###.#####.","##@.##....","##.$#..##."}

    Returns: 5.0

  14. {"##$#..$$..","....###.@.","###..###.#","####.#####",".####.#.##","..##.#$##.",".#.#.#..#.","###.######","##.###.###"}

    Returns: 10.133333333333333

  15. {"#..#..#..",".##.....@","....##...","....#.#..",".....$...",".#.......","..#......",".#.......",".#..##...","..#......"}

    Returns: 151.03282732239734

  16. {"...$......","..........","...$.....$","$.........","......$...",".....$....",".......$..",".........@","..........",".........."}

    Returns: 30.45012400742604

  17. {"@.#..#....","##..#....#","##.....#..","#.##......",".##..#.#..","##..#....#","..#...#..#","#......#.#","..$.......","#.#......."}

    Returns: -1.0

  18. {"###.##..##","$..@##..#.",".##.##..##","...#.....#","..####...#","##.#.....#","##..##.###","##.##.....","#.....#...","#.##....##"}

    Returns: 20.99999999999999

  19. {".#.###.#..","..........","..$#$.###.","#.#..#...#","..#.#.#..#","##..###...","#..#.#.#..","##.#..#@..","#..##.#..#","#.......#."}

    Returns: 956.4999999999698

  20. {"..#.#####.","#####..###","#.#######.","###.#..###","..###$##.#","..#######.","#.########","#########.","#####.#@#."}

    Returns: -1.0

  21. {".##.....#","#$...##..","......##.",".#.......",".........","....#.#..",".....#.#.","....#.#..","..#.@....","........."}

    Returns: 332.4079666605024

  22. {"..........",".@........",".......$..","..........","..........","....$.....","..$.......","...$......","$.$....$..",".........."}

    Returns: 56.71594851381519

  23. {".#...#.###",".###.#.##.",".#.##....#","..#.##...#","#.$.#####.",".#..####.#","#..##..@.#","##.#....##","##........",".#.#.#...#"}

    Returns: 387.40572937829705

  24. {"...#..###",".##..#.#.",".$.$#.#.#","##.##...#","$#....$@$","#....#.#.","...#$$#..",".#$##.#.#","#$....#.#","##$##...."}

    Returns: 3.2618943571601977

  25. {"###.###...","#......#..","#.#..#####","...##@..#.","####...$#.",".#....#.##","#.........","#.###..###","#...#####.",".#.##.#..."}

    Returns: 40.7842003372259

  26. {"##..###$.#","..#.##.###",".####..###",".######..#","#...##.#..","###@.###.#","##.##.#.#.",".#..##.###","##.###.##."}

    Returns: -1.0

  27. {".$..$$$.$.","....$$..$$","$......$..","$...$..$$.",".....$...$",".$....$$.$","$.$$.$$$$$","$$....$...","..$@..$$..","$.$$.$..$."}

    Returns: 2.8174232602386042

  28. {"$$$$$$$.$$","..$.$$..$$","$$$$$$.$$$","$$$.$$$@$$",".$..$$$$$$","$$.$$$$$$$","$$$$$$$.$$","$$..$$$$$$","$$$$$$$$$$","$$$$$$..$$"}

    Returns: 1.0

  29. {"#..#..#",".##....",".$##.#.","##..#.#","###.#..","....@..","##.#..#"}

    Returns: -1.0

  30. {".##......#","...@..#..$","..#.....#.","..#.#.##..",".#.#.##.#.","###...##..",".##.###..."}

    Returns: 211.9717261904743

  31. {"$@$##$$###"}

    Returns: 1.0

  32. {"#","#","#","#","#",".","$",".",".","@"}

    Returns: 9.0

  33. {"..","..",".@","..","..","##","..","#$","..",".."}

    Returns: -1.0

  34. {".#...##@..","........$#"}

    Returns: 17.999999999999957

  35. {"#.....#.#.","..@###$...","#.#..##...","...###...#","..#.#.....","..#.#..#..","###.####.#","#.#..##.##",".####.....","#.##..##.."}

    Returns: -1.0

  36. {"#..##..##$","#.#.##@.#.","....####..","##..#.###.",".#.#.###..",".###..###.","#####.#.#.","####......","..##....#.","..#.#.#.#."}

    Returns: -1.0

  37. {".#.###.#..","..........","..$#$.###.","#.#..#...#","..#.#.#..#","##..###...","#..#.#.#.@","##.#..#$..","#..##.#..#","#.......#."}

    Returns: 50.36075268817196

  38. {".####.#..#",".######..#","#.#..#.#.#","##.#..#..#","#..@######","...#.....#","#.#.....##",".#.$#...##","####.###.#"}

    Returns: -1.0

  39. {"....##...",".$.....$.",".....#...","$..$$$...","..###.#$.","..$.#...#","..#.#.#..","$.#......","#.#....$$","...#.@..#"}

    Returns: 20.951614980453304

  40. {"..........",".$..$.....",".......$$.",".@........","..........","..........","..........",".......$..","....$$....",".........."}

    Returns: 31.509908785243812

  41. {"#.$#####..",".#..#.##..","#..#..#.#@","..#..###..","##.##.#..#","......#...",".#.#...#..",".........#",".#.#.##.#.","....##...#"}

    Returns: -1.0

  42. {"$#####$#.","##..#$..#","#@$#$$$..","$$#.#.#..","#....##.$","##$$...##","..$..$.$#","#$$#..#$.","#.#$.$#..","....$#..#"}

    Returns: 1.0

  43. {"###.###...","#......#..","#.#..#####","...##@..#.","####...$#.",".#....#.##","#.........","#.###..###","#...#####.",".#.##.#..."}

    Returns: 40.7842003372259

  44. {"#$$#@.$$$#","##$$.#.$#$","##.#$.####","$.####$.#$","#$$#.##.#$","##$$$###$#","$$$#$#..$.","##$##.####","####..#$##"}

    Returns: 3.4285714285714284

  45. {"..#......","#........","###......","....#...#",".#.....##","#.###....",".#.......",".....#...","@...#.#..","#.#.#.$.."}

    Returns: 653.5889405620787

  46. {"......$.$.","..$.......","..$.......","$.........","..$...@..$",".........$",".....$$...","..........","..........","..$......."}

    Returns: 16.475982592477454

  47. {".....#.","##.####","#...#..","####..#",".....##",".....#@","#.##.$."}

    Returns: 4.0

  48. {"@.........","..........","..........","..........","..........","..........","..........","..........","..........",".........$"}

    Returns: 542.1005216813751

  49. {"..........","..........","......@...","..........","..........","..........",".$........","..........","..........",".........."}

    Returns: 262.5270845919832

  50. {"..........","..........","..........","..........","..........","..........","..........",".........@",".........$",".........."}

    Returns: 143.45236102932054

  51. {"..........","@.........","..........","..........","..........","..........","..........","..........","..........",".........$"}

    Returns: 541.1005216813702

  52. {"..........","..........","..........","..........","..........","..........","..........","....@.....","..........","$........."}

    Returns: 432.21887082128563

  53. {"..........","..........","........@.","..........","..........","..$.......","..........","..........","..........",".........."}

    Returns: 222.71550647859513

  54. {"..........","..........",".@........","..........","..........","..........","..........","..........","$.........",".........."}

    Returns: 377.1278552603537

  55. {"..........","..........","..........","..........","..........","..........","..........","..........","...@......","........$."}

    Returns: 359.3032035553276

  56. {".....$....","..........","........@.","..........","....$.....",".....$....","$.........","..........","..........",".........."}

    Returns: 56.754721096906565

  57. {"..$.......","..........",".$........","..........","........@.","..........","..........","....$....$","$..$......","..$......."}

    Returns: 59.268487169174875

  58. {"#..#..#...",".........@","..#.......","..#.#.....","$........#",".#..#.....","#......#.#","....##...#","#.....$..#",".#..#....."}

    Returns: 170.60521299081128

  59. {".....#$#..","........$.","#$.#......",".....#...#",".#....$..@","..........",".....#....",".....#...#","...#..#...","#....#...."}

    Returns: 43.99864177785296

  60. {"....#.#.#.",".#.....#.$","......@.#.",".........#","...#......","#$#.#....#","#.....#..#","......#.#.",".........#",".........."}

    Returns: 268.39920014038364

  61. {"..$....#..","....$...#.","...$#....#","......#..#","..........","..#.....@$","....#.....","......$..#","..#.......","........#."}

    Returns: 18.659186954690377

  62. {".....##...","..#.......","..........","..#.#...#.","...$..#.#.","......#...","..........","..........","$....$....",".@......#."}

    Returns: 19.796741148893222

  63. {"......#...",".......#..","........$.","..........","..$#.$...@","#..$.#...$","..........","..$#......",".#.......$",".........."}

    Returns: 9.328833398505584

  64. {"....##....","...$...@..","....#..$..",".........$","...#......","#......$..","...$......","...$......","......$...",".........."}

    Returns: 11.864333921499494

  65. { "@.........", "#########.", "..........", ".#########", "..........", "#########.", "..........", ".#########", "..........", "#########$" }

    Returns: 2915.999999999952

  66. {"@..............",".##############","...............","##############.","...............",".##############","...............","##############.","...............",".##############","...............","##############.","...............",".##############","..............$"}

    Returns: 15679.99999999979

  67. {"$..............",".##############","...............","##############.","...............",".##############",".......@.......","##############.","...............",".##############","...............","##############.","...............",".##############","..............$"}

    Returns: 2910.999999999966

  68. {"$..............",".##############","...............","##############.","...............",".##############","..@............","##############.","...............",".##############","...............","##############.","...............",".##############","..............$"}

    Returns: 2735.9999999999745

  69. {"@..............",".##############","...............","##############.","...............",".##############","...............","##############.","...............",".##############","...............","##############.","...............",".##############",".............#$"}

    Returns: -1.0

  70. {"....@..........",".............$.","......$........","...............",".$.............",".............$.","....$..........",".......$$......","...............","...............",".$.............","...$...........",".........$.....","..........$....","$...........$.."}

    Returns: 38.07037723734559

  71. {"...............","...............","........$......","............$..","...............",".$.$...........","......$........","...............","$..............",".........$.....","...............","...............","...............",".............@.","........$......"}

    Returns: 85.00876730515527

  72. {"...............","...............","...............",".........@.....","...............","...............","...............","..$............","...............","........$..$...","...............","...............","...............","...............","$.....$...$...."}

    Returns: 174.9205072427839

  73. {"...............","...$...........","...............","....@..........","..$...........$","..$............","..$$...........","...............","...............","...............","...............","...............","...............","...............","...........$..."}

    Returns: 54.82969652806735

  74. {"...............","...............","...............","...............","..............$","...............","...............","..........$....","...............","......$.......$",".....$..$......","...............","...............","...............","@.............$"}

    Returns: 127.16320625877697

  75. {".......$.....$.","..............$","..............$","...............","...............","...............","...............","...............","...............","...........@...","...............","...$...........","...............","...............","..............."}

    Returns: 229.87237066998227

  76. {"....@..........","...............","...............","...............","...............","$..............","...............","...............","...............","...............",".............$.",".............$.",".............$.","...............","..............."}

    Returns: 269.79379316926344

  77. {".##.....#......","#...#.....#.#..","...#...........","............$##","........@##.$..",".$.....#...#...",".#....##..#....",".......#..#$.#.","..##...#.....#.",".............#.",".......#..$....",".####..#..$.#..","$....#..#...#..","##......#...#..","...#....$...#.#"}

    Returns: 100.52759116244174

  78. {"##.#......#$...","#..##.....#....","...##.#..#.....",".....@.$...#..#","...#...##.#....","....#...#.#...#","....#..........","..#...........#","..##.#.......#.",".#...$#......$#","...#.........##","...#....#......",".##............","....##.#..$..#.","..........#..#."}

    Returns: 101.99560497653198

  79. {".......##......",".#.#.....#....#","......#........","........##.@...",".#..........#..",".....##....$...",".....#...$$#...","#..#.###..#..##","...##..#.....#.",".$..##....##.#.",".....$......#.#","...$...........","#.....#....###.","....#..$.#.....","#....$.$..#.#.."}

    Returns: 79.32213030140709

  80. {"......#.....##.",".....$.........",".#......#..#...",".....##$..@#...",".........#.....","#...$.#.....###",".#.#.##.#.....#","#..#..#........","......#....#..#",".....##..#.....","..........#..#.","#.....$....###.","##..#...##...#.","......#.....###","....#.........."}

    Returns: 120.3379742258571

  81. {"..##..#..##..##","#....#...@.#...","##...........#.","....##..#.#..#.",".#.##.#....##..","...#......###..",".......#.....#.",".....#.#......#",".#$#...........",".....##.......#","....#.$.#......","#....$...##....","#.##.$..#...#..","#.....###....#$","......#...$.#.."}

    Returns: 358.87258648867953

  82. {".....#........#",".#....#......$.","...#...#......#","....#....$#..#.","...#.....#.....","#...#....#.....","#.##.#..#......",".#..#.#........","...#...#...#...",".###..##.#.@.$.","$.#..#.........","###......##.#..",".....##.....#.#","..........#.#$.","....#....#...#."}

    Returns: 137.20112892428736

  83. {"$..#...........","..#...####.#...",".....#.........",".............#.","#.#....$....##.","##......#....#.","......#$.......","#.....#........","##...#.......#.","..#....##......","#..###.#.......","......#....@...","....$.......#..","#.#..........#.","$.$#.....#.#..#"}

    Returns: 180.31119019476847

  84. {"..#....#.....$.","........#$#....",".....#........#",".......#...#...",".#........##...","..#............","...#..#.......#",".#...#...#.#...",".#........#....","$....#..#.#..##","...###.#.#.....","...##.......#..","#.##...#.......","........##.##..","..#..#.#.@....."}

    Returns: 492.9132760578129

  85. {"$..............","...............","...............","...............","...............","...............","...............","...............","...............","...............","...............","...............","...............","...............","..............@"}

    Returns: 1481.1247777074964

  86. {"...............","...............","...............","...............","...............","...............","...............","........$......",".........@.....","...............","...............","...............","...............","...............","..............."}

    Returns: 261.3340054150918

  87. {"..............@", ".##############", "...............", "##############.", "...............", ".##############", "...............", "##############.", "...............", ".##############", "...............", "##############.", "...............", ".##############", "..............$"}

    Returns: 15875.999999999409

  88. {"$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$@$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$","$$$$$$$$$$$$$$$"}

    Returns: 1.0

  89. {"###############","###############","##@############","###############","###############","###############","###############","###############","###############","###############","###############","###############","###############","##########$####","###############"}

    Returns: -1.0

  90. {"###############","###############","##@$###########","###############","###############","###############","###############","###############","###############","###############","###############","###############","###############","##########$####","###############"}

    Returns: 1.0

  91. {"##....#....#", ".@..........", "..#.#..##...", "..........#.", "#.#.##......", "........#..#", "##.##..#...#", "...........$" }

    Returns: 625.3353944106268

  92. {"@#...#.........", ".#.#.#.#.#####.", ".#.#.#.#.#.....", ".#.#.#.#..#..##", ".#.#.#..#..#...", ".#.#..#..#.###.", ".#..#.#..#.#...", "..#.#..#.#.#.##", ".#...#.#.#.#...", "..#..#.#.#..##.", ".#..#..#..#.#..", "..#.#..#.#..#.#", ".#...#.#.#.#...", ".###.#.#.#.#.#.", ".....#...#...#$" }

    Returns: 9833.54271356619

  93. {"...............", "...............", "...@...........", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...........$...", "...............", "..............." }

    Returns: 756.4572038411387

  94. {"..............$", "...............", "..#............", "...............", "........#......", "...............", ".....#.........", ".......@.......", "...............", "...............", "...#...........", "........#......", "...............", "...............", "$.............." }

    Returns: 587.0693340648039

  95. {"@..............", "##############.", "...............", ".##############", "...............", "##############.", "...............", ".##############", "...............", "##############.", "...............", ".##############", "...............", "##############.", "$.............." }

    Returns: 15875.999999999409

  96. {"@#...#...#...#$", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", ".#.#.#.#.#.#.#.", "...#...#...#..." }

    Returns: 15875.999999999409

  97. {"$..............", "############...", ".............#.", ".#.###########.", "............#..", "###########...#", "............#..", "..#############", "...............", "#########.#.##.", "...............", "....###########", "...............", "############.#.", "@............#." }

    Returns: 9528.610688882774

  98. {"@..............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "##########.####", "$.............." }

    Returns: 9701.451867289377

  99. {".$............$", "..............$", "...............", "...............", "...............", "...............", ".......@.......", "...............", "...............", "...............", "...............", "...............", "...............", "$..............", "$............$." }

    Returns: 215.2550427873787

  100. {"$..............", "##############.", "...............", ".##############", "...............", "##############.", "...............", ".##############", "...............", "##############.", "...............", ".##############", "...............", "##############.", "@.............." }

    Returns: 15875.999999999409

  101. {"@..............", "##############.", "...............", ".##############", "...............", "##############.", "...............", ".##############", "...............", "##############.", "...............", ".##############", "...............", "##############.", "..............$" }

    Returns: 12543.999999999749

  102. {"$..............", "############$#.", "...............", ".##############", "...............", "##############.", "...............", ".##############", "...............", "##############.", "...............", ".##############", "...............", "##############.", "@.............." }

    Returns: 11861.067961165503

  103. {"..............$", ".##############", "...............", "##############.", "...............", ".##.###########", "...............", "########.#####.", "...............", ".##############", "...............", "##############.", "...............", ".##############", "..............@" }

    Returns: 13698.399999999043

  104. {"..........###.$", "..####.....####", "............##.", ".......####....", "..##...........", "..##.....####..", "...............", "........@..##..", "...............", "..#############", "...............", "#####..........", ".$##...........", "..#..#########.", "..#..........$." }

    Returns: 4228.933568898264

  105. {"@..............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "...............", "..............$" }

    Returns: 1481.1247777074964

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: