Statistics

Problem Statement for "CoinsGameEasy"

Problem Statement

We are playing a game with a pair of coins on a rectangular board. The board is divided into unit square cells. Each cell is either empty, or it contains an obstacle. The board is given to you as a String[] board. The character '#' represents an obstacle, '.' is an empty cell, and 'o' is an empty cell with a coin. You may assume that there are exactly two coins on the board, and that initially they lie in different cells.


Next to the board, there are 4 buttons labeled "Left", "Right", "Up", and "Down". The game is played by pushing these buttons. When you push a button, all coins will try to move one cell in the corresponding direction. For each coin, there can be three different outcomes:
  • If the next cell in the chosen direction contains an obstacle, the coin remains in its current cell.
  • If there is no next cell in the chosen direction (i.e., if the coin is already on the corresponding edge of the board), the coin falls off the board.
  • In all other cases, the coin moves one cell in the chosen direction. Note that this includes the case when the destination cell currently contains another coin.



The goal of the game is to make exactly one coin fall off the board. If that is impossible, or if you need to push more than 10 buttons in order to achieve the goal, return -1. Otherwise, return the smallest number of times you need to push a button in order to achieve the goal.

Definition

Class:
CoinsGameEasy
Method:
minimalSteps
Parameters:
String[]
Returns:
int
Method signature:
int minimalSteps(String[] board)
(be sure your method is public)

Notes

  • There may be some sequences of moves that will cause both coins to end in the same cell. Note that when trying to win the game such moves should be avoided.

Constraints

  • board will contain between 1 and 20 elements, inclusive.
  • Every element of board will have the same length, and this length will be between 1 and 20, inclusive.
  • Each character in each element of board will be one of '#', 'o' and '.'.
  • There will be exactly 2 'o' in board.

Examples

  1. {"oo"}

    Returns: 1

    Push the Left button. The left coin will fall, the right one will move one step left and it will still be on the board.

  2. {".#", ".#", ".#", "o#", "o#", "##"}

    Returns: 4

    You need to push the Up button 4 times in a row.

  3. {"..", "..", "..", "o#", "o#", "##"}

    Returns: 3

    As in Example 1, this game can be won by pushing the Up button 4 times. However, there is also a shorter solution: push Up, Right, and Right, in this order.

  4. {"###", ".o.", "###", ".o.", "###"}

    Returns: -1

  5. {"###", ".o.", "#.#", ".o.", "###"}

    Returns: 3

  6. {"###########", "........#o#", "###########", ".........o#", "###########"}

    Returns: 10

  7. {"############", ".........#o#", "############", "..........o#", "############"}

    Returns: -1

    You need at least 11 steps to win the game, so you should return -1.

  8. {"##..#",".#o#.","#.###","..###","#####","#####","#o..#","##...","#####","###..","#####",".#..#","#####","###.#","#####","#.##."}

    Returns: 2

  9. {"...#......","..#.......","....#..###","#..#....#.","#.........",".......##.",".......o..","..#...##..","o........."}

    Returns: 1

  10. {"##..#",".#o#.","#.###","..###","#####","#####","#o..#","##...","#####","###..","#####",".#..#","#####","###.#","#####","#.##."}

    Returns: 2

  11. {"#.....#..####o..###","..##...####.##..##.","##..####..o#.##..#.","..#.##.##..##..#..#","###....#..##..###.#"}

    Returns: 1

  12. {".#..o.#.#...#....",".#.###..#o..#...."}

    Returns: 1

  13. {"#.....#...#..##...","..#o..#..#......#.","..#..##....#.....#","##...##.#......###",".....#...####..##.","..#....###.##.#...","#.....##..#.##....","...#..#..##.#.....",".#.###..o..#..#..#",".#......#..#.....#"}

    Returns: 2

  14. {".#########..","#######.####","############","########..#.","...##.######",".###..#.####","..##########","######o#####","###o####.###","#####.#####.","#######.#.##","##.#####.#.#","####.##.####","######.##.##","###....####.","##.#######.#","############","###.####..#.","######.#.##."}

    Returns: -1

  15. {"###","o#o","###"}

    Returns: 1

  16. {"....#........","..#o.#.......",".#........##.","....####....#",".......##....","##.....#..#..","#....#..#.##.","....o##.#..#.","..........#.."}

    Returns: 2

  17. {".#..#####",".#..o..#.","..#####.#","####.##.#","#.####.##","#.#.#.##.","###.####.",".#.##....","#.#.#.###","..#.####.","##.#.o##.","####..#.#","..#..#.##","##.###.##"}

    Returns: 3

  18. {".o#.##","##o.##","######"}

    Returns: 1

  19. {"....##.##o..#.##.",".#......######.o#"}

    Returns: 1

  20. {"#.#####.####","############","#.#####.####","##########.#","#..##o..#...","####o#.##.##"}

    Returns: 1

  21. {"#########.##.###","#.#####.#.######","..####.#####.##.","###.###...###.##","##...#######.###","######..##..####","################","#.#.####.#######","################","###.##.#####.###","##.###..##.#####","#.##.#.##.####.#",".#####.##.######","#..###.##.######","#############oo#",".###########.##."}

    Returns: -1

  22. {"..........","..........","..........","..........","..........","..........","..........","......o...","..........","..........","......o...","....#.....",".........."}

    Returns: 3

  23. {"#.#.#.#.###","##...#.#.##",".#..#o.#...",".#.##.##..#","#....####.#","####.#..o##",".##...##..."}

    Returns: 2

  24. {"..o..............",".................",".o...............","................."}

    Returns: 1

  25. {".#.#....#...###.","#..#..###.#oo#..","...#.....#.....#"}

    Returns: 2

  26. {"#.","##",".#","##","o.","o.","##",".#",".#",".#","##","##","#.",".#","..","..",".#"}

    Returns: -1

  27. {"...o..#.","..##...#",".....#.#","###.##..","..##....","........","..###.##",".#.#.#.#","..#....#","..#...o.",".......#","##.#....","#.#...##"}

    Returns: 1

  28. {"..#..##.####","#....#######","########.###","####..######","##.#o#######","#.###.####..","############","#####.######","####.#.#.#.#","############","###.####.##.","#########..#","########.###","#..#####o###"}

    Returns: 1

  29. {"....#........",".......o.....","......#......","...##........",".............",".#...........",".#.....#...#.",".............","#............",".........#...","........o..#."}

    Returns: 1

  30. {"###.###","###.###","###.###","##..##.","#####.#",".######","#####..","####o##","#####o#","##.####"}

    Returns: -1

  31. {"...#.#.","##..o.#","...#...","..o#..."}

    Returns: 1

  32. {"###",".##","###","###","###","o##","#o#","###","###"}

    Returns: 1

  33. {"#####.#..#######.##",".###.#####..##...#.","##.#.#..####..#####",".##.#...###..##..o#","..##.########.##.##","..######..#..#...##","####..#.#.####.###o","###.#.##.#..###.#.#","######..##.##...###"}

    Returns: 1

  34. {"#..##.####",".##oo.#.#.",".#..#..#.#","..#.##.###",".##.#..##.",".###.#.###","#.#.#.....","##..##.###","#.#...#.#.","....###..#",".#.#.##...","..##..###.","....#.#..#",".##..#.#.#","...#..#..#","###.##.#..","###...###."}

    Returns: 3

  35. {"..#..o.....",".......o..."}

    Returns: 1

  36. {".o..#.....#..#","#...#..o.###.#",".#............",".............."}

    Returns: 1

  37. {"#.#.o","#.#..",".####",".#.#.",".#.#.","#..##","...o#","##.#.","...##","#...#",".####","###..","##.##","##..#",".....","##..#"}

    Returns: 1

  38. {"#########","#########","########o","o########"}

    Returns: 1

  39. {"#########.#########","############o######","######.#o#####.####","####.#.#####.######"}

    Returns: -1

  40. {"....#o##.#....","...##...o....#"}

    Returns: 1

  41. {"#..##..######.##...",".####.##...##.#...#",".########.#..##...#","##.####......#.##.#","#.#......#..o.#..#.","#.##.#####..##.#.#.","..#.....##.##.#####","#.##.#....#.#..##.#","####.#.#.##.....#..",".#.....##.....#####","..o#..#...#...##.#.","...##..####.#...#.#"}

    Returns: 2

  42. {"..#.#...#","..o......","###.....#",".........","..#......","...##....","##..##...","........#",".##...#..","#..##....","#.#..#..#","........#","....##.o.","#..#.....","...#....."}

    Returns: 2

  43. {".#.o.#","#.#o.."}

    Returns: 1

  44. {"####.##.###","#.###..#.##","####....#..","..#.##o.##.","#..##o#####","#.##.####.#"}

    Returns: -1

  45. {"........#........",".................","#........#.....#.","...........o.....","...#........#....","#................","....#............","#......#....o....",".............#...",".......#..#......",".................","...............#."}

    Returns: 4

  46. {"#####","##.#o","..###","###.#","#####","#.o##","#####"}

    Returns: 1

  47. {"#...#.##..o.##.####","......#.........#.#",".#.##..#..#..#...#.","..######..##.#....#","#...#.#..#....#o..#",".#...#.#..##..#..##","...###..#...#..#.#.","...###..#####.#....","..#..##.#..#..#.###","#.....###..##.....#"}

    Returns: 1

  48. {"..........#.......","..................","..................",".............o....","..................","..#........#......","..................","...........#.....#","..................",".#.....o.........#"}

    Returns: 1

  49. {".o.#...","#......",".#..o..","......#",".......",".......","..##...",".....##","......."}

    Returns: 1

  50. {".#####.","#######","###.##o","#.#####","#.###..","#.#####","#######","#.#####","###.###","o######","##.####",".###.##","...##.#"}

    Returns: 1

  51. {".#.###","#####.","#.#...","#.###.",".o.#..","#..###","##.###","###.##",".##.##","###.##","##..##","###o#.","#####.","####.#",".#####"}

    Returns: 2

  52. {"#####.##########","#############.##","#######o########","################","################","#####.#########.","################","######.#########","###########.##.#","###########o####","################","################"}

    Returns: -1

  53. {".....o#.....","..##..o.#.##",".....#.....#"}

    Returns: 1

  54. {"#####","#####","###o#","o####","#####","#####"}

    Returns: 1

  55. {".............","...#.....#...","#....##....#o","....###..##..",".#.....#.....","......#...#..","...#.....#..#",".....##......",".####o....##.","##....#....#.","...#..#......","#.#..#.#.#...","#........#...","#.......##..."}

    Returns: 1

  56. {"##.###############","##################","############o#####","###############.##","##############.#.#","##################","######.###########","#################.","#..##############.","#######.##.#######","##########.#######","###############.##","###############.##","#########.######o#","########.#########","##################","##################"}

    Returns: -1

  57. {"##...#...#..........",".....#.....#.##.##.#",".#.#.....o...#...#.#","#......#.#...#.##...","......##....#.###...",".........#.###...#..",".#...#......#.......",".#####.#........#...",".#..................",".....#......#.......",".#...##..##....#....","#.....#.##.o.#...#..",".##......#......#.#.","#...#..#.#...###....","...#.#......#.#.....","...#.....##......#..","...#...###.....#.#.."}

    Returns: 4

  58. {"......#.#","###...#..","#..##...#","##......#","#..#....#","o#..#....","#..#....#",".........","##.##....","#..##...#","##...##..","#.###.#..","......#o."}

    Returns: 1

  59. {"......","......",".....#","......","...##.","##....","#..#..","##....","##....","......","......",".o....","..#...","#..#..","...#.#","......","#o..#.",".#....","......","......"}

    Returns: 2

  60. {"##..##.##","##.##.###","##..#####",".########","#########","###.o.###","#########","##.######","#o#####..",".##.#.#.#","#..####.#"}

    Returns: -1

  61. {".#....","..#.o.","...##.",".....o","......","....#."}

    Returns: 1

  62. {"..","..","..","#.",".o","##","#.",".#","..","..","#o"}

    Returns: 1

  63. {"##o#.########","#..#.#..#####","o#####.#.#.##"}

    Returns: 1

  64. {"###############","####.###..#.###","##########.####","#o#############","###.#########.#","######.########","#############.#","########.###.##","##.############","###.##.#.######","###############","########.###.##","####o##.#######","###############"}

    Returns: -1

  65. {"o#.#.#.#","#.#..##.",".##...##","#.####o.","#####...","..#..###","##.#.#.#",".##.###.",".....#.#","...#####",".##.####"}

    Returns: 1

  66. {"###..##.#..#....","..####.......o..",".##.###..##.##o#",".#.##..##.#...#.","..#.####..####..","##..##.#.#.###.."}

    Returns: 2

  67. {"...","...","o.o",".##"}

    Returns: 1

  68. {"#.####..###.###.#.","..##.#..#####o..##","#.#..#####.####..#",".##.#....#####.###","###..#.#..##..####","#.##.#.#..#.#####.","...#...#..##.####.","###.#.######.#####","...##.#.#...#..#..","##.#.####..##.#.##","....#.o...##..###."}

    Returns: 1

  69. {".......",".......","..o....",".......",".......",".......",".......",".......","......#",".......",".......",".......",".......",".......","..o....",".......",".......",".......","......."}

    Returns: 3

  70. {".o..##",".#.##o"}

    Returns: 1

  71. {".#","##","##","##","o#","o#","#.","##","##","#.","##",".#","##"}

    Returns: -1

  72. {"#.....#..","........#","#........",".#.#..#..",".......#.",".........",".........","o........","......#..","......#.#","......o..",".........","...#.....",".......#."}

    Returns: 1

  73. {".........","...o.....","....#....",".o....#..",".........","........#"}

    Returns: 2

  74. {".##.##","###.##","####.#","####oo","##.#.#",".####.","#.##..","#.####",".###.#",".#.###",".#####",".#.###",".#..#.","##.#.#","######"}

    Returns: 1

  75. {"...o.#...",".........","#....#..#",".........",".........",".........",".......o.","....#....",".........",".........",".........","......##."}

    Returns: 1

  76. {"o####","#####","#####","#####","#####","#####","#####","###o#","#####","#####","#####","#####","#####"}

    Returns: 1

  77. {".##########o##",".#o.##########"}

    Returns: 1

  78. {"..##.#......#.##.","........##.#.....",".......#...#.#...","o..##...##.##.#..","..#..#...###.....",".###..#..#...#...","...#....#...#...#","..#####.....#..#.","##...#...##...#..","#.....##..##....#",".#.##...#........","####........#.#.#",".#...##.#o.....#."}

    Returns: 1

  79. {"#.##",".###","..##","...#","#.o.","##.#",".o##","...#","##..","#...","#...","####","##.#"}

    Returns: 2

  80. {".#....","#..#.#",".....#","......","#....#","..###o","#....#",".#....","#.####","......","##.#.#",".#...#",".#..#.","...##.","#..#..",".###o#"}

    Returns: 1

  81. {"#......##.##.##",".....##..#..###","..#..###.#.#..#","###o#####o#..##","..##......#..##"}

    Returns: 2

  82. {"...##.#..##...#.#","###.##.##.##.#.##",".##...#.###.....#",".##.#..#..##.#.#.","#..##..#.......#.","###.#......##..#.",".###...###...###.",".###.o#..#.###.#.",".#####..#..##.#.#","##.##..##..#....#",".#####.#.#####..#",".#.##.####.##o.##",".#####....#.#.##.","#####.##.#..#..#.","#..##.#.##.######"}

    Returns: -1

  83. {"#...#.....##..",".#.#.#........","#.#.#......#.#",".#.#......##..","....#....#....",".#.##...#...#.","...o.....###..","......#..#o...",".#...#.#..#...",".......#.##.#.","..............","...##..#......","...###.#.....#"}

    Returns: 4

  84. {"........","........","........","........","....#...","........","........","........","........","...o....","........","....#...",".....o.#","....#...","..#.....","........","#......#"}

    Returns: 4

  85. {"........","........",".....#..","........","........","........","........","........","...#....","........","o.......","o.......","......#.","#...#..."}

    Returns: 4

  86. {"....#..",".o#....","..##...","..#.#..","#...#.#","#...#..","...#...","....##.",".......","...#..#","...o...",".......",".......","....#..","......."}

    Returns: 2

  87. {".#..###.####.#.#.##","##...#.##.#.#..#.#.","#.##.#.#.###.......",".#....##........##.","#......#...#.#..###","..#.#.#..........#.","#....######.....##.",".....##......#....#","..####.####.....##.","..#..###.#.#....#..","#.......#.#....#...","...####.....o#...##","..#...#.####..#..#.","..####....#.##.###.","#..#.......#.##.##.","##......#.....#....","#..#.#.###....##o#.",".#.......##..#.#...","......#####......#."}

    Returns: 3

  88. {".##.#...##..",".#.##.....##","....###.....","#.#....o..#.",".##....##.#.",".#####..#.#.","##..#o#...#.",".##..#.....#","..###..###..",".##.###..###",".##..##.#...","#.#.##..#..#",".......#....","#......###..","#..#....#.#.","#.#....#.###","##.#.###.#.."}

    Returns: 4

  89. {".#...#","#.....","......","#..#..","......","..#o..","..o#..","....##","......","..#..."}

    Returns: 3

  90. {"...o..#......",".............",".............",".............",".............","...#.........",".............",".....#....#..",".............",".............",".............",".............",".............",".............",".......#.....",".............",".............",".............",".............","..#o........."}

    Returns: 1

  91. {"..o.","#o.#",".###","####","#.#.","##..","..##","####",".###","####"}

    Returns: 1

  92. {"#o###","##.#o","#.###"}

    Returns: 1

  93. {"#################.##","########.#.########.","##.#.#######.##.####","################.###","#.#####o############","#########.##########","#######.##.#########","####.######.#######.","########.####.######","######..#########.##","#########.##########","##################o#",".######.######.#####","##.#########.###.###","######.###.#####.###","####.#########.#####","#.###.##.###.#.###.#","###.################"}

    Returns: -1

  94. {"###..####.######.","########.########",".###.###..###.#.#",".#o####.#########","##########..#####","############.####","######.##.#######","#################","##.#######.####.#","#####.o.#####.###","#####.##.#.##.##.","########.###..###","#################","#############.###","##############.##","#.###############","#####.###########"}

    Returns: -1

  95. {"#...","....","###.","....","...#","o#.#","#.#.","..#.","..#.","o..#","...#","..#.","....","...#"}

    Returns: 2

  96. {"..........","........#.","...o......","..........","..........","........#.",".#........","..........","..........","#.......o.","..........",".........."}

    Returns: 2

  97. {"...o#","##.##",".#.#.","....#","...##",".#...","..o.#","##..."}

    Returns: 1

  98. {".#.....#..","#...#..#.#",".##.##...o","..##..#..#",".#...##...","....##....","###...#...","##..####.#","..o##....."}

    Returns: 1

  99. {"...........",".#...#.#..#","####.#.#.#.",".....#...##","..#..#.....","...#.#...##","..#.o..#..#","..#.#.###..",".o#.....#.#","##....#.#.#","..#..#...#.",".##.#..#...","#.###.#....",".#####.....","#..##.##.#.","..#....#..#","###..#.#..#"}

    Returns: 2

  100. {"####.","##..#","#.###","#####",".#.##","#####","#o###","o..##"}

    Returns: 1

  101. {"#.#.#","..#..","#.#.#","#.###","#..oo","....#","#.#..","###.#","#.##."}

    Returns: 1

  102. {"..#","#.#","#..","...","...",".#.",".#.","...","...",".o.","...","...","..o"}

    Returns: 1

  103. {"o.....","...#..","......","......","..o...","....#.","..#...","......","......","......","......","......","......","......"}

    Returns: 1

  104. {"##","##","##","##","##","##","##","##","##","##","##","#o","##","##","##","o#",".#"}

    Returns: 1

  105. {"...#...#...##..o###.","#.#..##..####...#.#.","....#.###......o#..."}

    Returns: 1

  106. {".#.##.#..##.##.####","#####.####.#...###o","##.#....##..#.#####",".###..##.######...#","#.##.##.##...#.##..","#####.#######.##.##","#.##.#####..###.###",".###..o############"}

    Returns: 1

  107. {"...###o#",".##.###.","#o..##.#","#.###.##"}

    Returns: 1

  108. {"...#",".#..","..o.","#...",".o..","#...","....",".#..",".#..","....",".#.#","....","....","....","#..#","...#","....",".##.","....","##.."}

    Returns: 2

  109. {"##########","...#o...##","..####...#","........##","##########","##########","...#o...##","..####...#","........##","##########"}

    Returns: -1

  110. {"##########","...#o...##","..####...#","........##","##########","##########","...#.o..##","..####...#","........##","##########"}

    Returns: 10

  111. {"##########","...#o...##","..####...#","........##","##########","##########","...#o...##","..####...#","........##","#######.##"}

    Returns: 7

  112. {"###", ".o.", "#.#", ".o.", "###" }

    Returns: 3

  113. {"....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", ".........o..........", "..........o.........", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "...................." }

    Returns: 10

  114. {".###", ".oo#", ".###" }

    Returns: 2

  115. {"############", ".........#o#", "############", "........o..#", "##########.#", "##########.#" }

    Returns: 5

  116. {"#######", "#.....#", "#.##.##", "#..#oo#", "##.####" }

    Returns: 10

  117. {"############", ".........#o#", "##########..", "..........o#", "############" }

    Returns: 3

  118. {"....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "..........o.........", ".........o..........", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "....................", "...................." }

    Returns: 10

  119. {"###################", "........o#.......##", "###################", "........o.........#", "###################", "..................#", "###################", "..................#", "###################", "..................#", "###################", "..................#", "###################", "..................#", "###################" }

    Returns: 10

  120. {"..####", "o.o..." }

    Returns: 1

  121. {"#####", ".o...", ".o...", "#####" }

    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: