Statistics

Problem Statement for "TreasureHunt"

Problem Statement

Hurray! You have found a map to a hidden treasure on an island somewhere in the Carribean. It's a classic pirate treasure map, with a big X marking the spot of the treasure. It also has instructions describing how to walk to reach the X, like "north 2 paces", "east 1 pace", etc. However, the instructions lack one vital piece of information: It doesn't say where on the island you should start from! Since you suspect the treasure is buried deep and that the X on the map is only a rough estimation, you might have to dig in a lot of places before finding the treasure. So before you start to dig, you pick up your laptop computer in order to determine where on the island the treasure is most likely to be buried.

You assume that the intended start location is somewhere on the beach, and that if you follow the walking instructions, you should never have to walk across water. If several such starting positions exist, the position that will cause the treasure to be closest (Euclidean distance) to the estimated treasure position is considered most likely (see example 0). If there is a tie, select the northernmost position of these. If there is still a tie, select the westernmost position of these.

The island will be given as a String[], where a dot ('.') represents water, uppercase letter 'O' represents a part of the island, and uppercase letter 'X' marks the estimated location of the treasure (this position is of course also part of the island). A square is only considered to be a beach if it's part of the island and is adjacent (in any of the four cardinal directions) to a water square. Squares outside the map are considered to be water squares as well (they are part of the ocean). Below is an example of a valid island. 

{"..OOOO..",
 ".OOOO...",
 "OOXOOOOO",
 "OOOOOOO.",
 ".OOOO...",
 "..OOO..."}

The island will always be connected. This means that if you stand somewhere on the island, it will be possible to reach every part of the island by only walking on land in any of the four cardinal directions. Also, there will be no lakes, which means that from any water square it will be possible to go in cardinal directions on other water squares until the edge of the map is reached.

The walking instructions will be given as a String[] where each element is in the form (quotes for clarity only) "<direction> <paces>". Direction will be either 'N' (decreasing y), 'S' (increasing y), 'E' (increasing x) or 'W' (decreasing x). Paces will be an integer between 1 and 9, inclusive. Walking one pace corresponds to moving one square.

Create a class TreasureHunt containing the method findTreasure which takes a String[] island and a String[] instructions describing the island and the instructions, respectively, in the formats above. The method should return a int[] containing the coordinates on the map where the treasure is most likely to be buried. The first element should be the x-coordinate (the first column being 0) and the second element the y-coordinate (the first row being 0). If the treasure can't be on the island, return a int[] containing zero elements (see example 4).

Definition

Class:
TreasureHunt
Method:
findTreasure
Parameters:
String[], String[]
Returns:
int[]
Method signature:
int[] findTreasure(String[] island, String[] instructions)
(be sure your method is public)

Notes

  • All land cells that are on the edge of the grid are considered to be a beach since they're adjacent to squares outside the grid, which are water (see example 2).
  • The Euclidean distance between two points x1,y1 and x2,y2 is sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)).
  • East is the positive x-direction and North is the negative y-direction.

Constraints

  • island will contain between 1 and 50 elements, inclusive.
  • Each element in island will contain between 1 and 50 characters, inclusive.
  • All elements in island will contain the same number of characters.
  • The characters in each element in island will be '.', 'O' or 'X'.
  • Exactly one character in island will be a 'X'.
  • The island will be connected.
  • The island will not contain any lakes.
  • instructions will contain between 1 and 50 elements, inclusive.
  • Each element in instructions will be in the form " " where direction is 'N', 'S', 'E' or 'W' and paces is an integer between 1 and 9 (without leading zeros), inclusive.

Examples

  1. {"..OOOO..", ".OOOO...", "OOXOOOOO", "OOOOOOO.", ".OOOO...", "..OOO..."}

    {"W 3","S 1","E 2"}

    Returns: { 3, 2 }

    The treasure can't be buried where the 'X' is, because then we would have to walk on water.

  2. {".......", ".OOOOO.", ".OOOOO.", ".OOXOO.", ".OOOOO.", ".OOOOO.", "......."}

    {"N 1"}

    Returns: { 3, 4 }

    Notice that you must start from the beach.

  3. {"OOOOOOOOOOO.", "OX..........", "OOOOOOOOOOO."}

    {"W 2"}

    Returns: { 1, 0 }

  4. {"....OO.", "..OOXOO", "OOOO...", ".OOOOOO", "...OOOO", ".OOOOO.", "..OOO.."}

    {"N 1","E 1","N 4"}

    Returns: { 3, 1 }

  5. {"X"}

    {"N 1","E 1","S 1","W 1"}

    Returns: { }

  6. {".................O..", "..OO.......OOOOO.O..", "..OOO..OOO.OOOOOOOO.", "..OOOOOOOOOOOOOOOOO.", "..OOOOOOOOOOOOOOOOO.", "...OOOOOOOOOOOOOOOO.", "OO.OOOOOOOXOOOOOO...", ".OOOOOOO..OOOOOOOO..", "OOOOOOOOO..OOOOOOOO.", "OOOOOOOOO..OOOOOOO..", ".OOOOOOOOO..........", "OOOOOOOOOOOOOOOOOO..", "..OOOOOOOOOOOOOOO...", "OOOOOOOOOOOOOOOOO...", ".OOOOOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOOOO..", "..OOOOOOOOOOOOOOOOO.", "OOOOO.OOOOOO..OOO...", "O..OO.OOOO.....OOO..", "O......O.OO......OO."}

    {"N 2","E 3","N 4","E 2","S 1","W 2","E 9","E 2", "N 3","W 5","N 1","W 6","N 6","S 1","S 1","E 7"}

    Returns: { 10, 6 }

  7. {"OXO."}

    {"W 2"}

    Returns: { 0, 0 }

  8. {".XOO"}

    {"W 3"}

    Returns: { }

  9. {"X.OO","O..O","OOOO"}

    {"W 1"}

    Returns: { 2, 0 }

  10. {"O.O.O.X.O.O","O.O.O.O.O.O","O.O.O.O.O.O","O.O.O.O.O.O","OOOOOOOOOOO"}

    {"E 2","E 2","E 2","E 2","E 2"}

    Returns: { 10, 4 }

  11. {"OOOOOOO.OOOOOO.O","...O.O..O....OOO",".OOO.OXOOO.O.O..",".O.........O.O.O",".O.OOO.OOOOO.OOO",".O.O.O.O.O.....O",".OOO.OOO.OOOOO.."}

    {"N 1","E 1","S 1"}

    Returns: { }

  12. {".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.X",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O","OO.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO"}

    {"E 1","N 1","S 1","W 1"}

    Returns: { 48, 49 }

  13. {".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.X",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O","OO.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO"}

    {"N 1","E 1","S 1","W 1"}

    Returns: { 0, 49 }

  14. {"OOOOOXOOOO"}

    {"E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9"}

    Returns: { 0, 0 }

  15. {"..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................X...............................","..................O...............................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................",".................................................."}

    {"S 1"}

    Returns: { 18, 23 }

  16. {".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......O.........................O................",".......OOOOOOOOOOOXOOOOOOOOOOOOOOO................","..................O...............................","..................O...............................","..................O...............................","..................O...............................","..................O...............................","..................O...............................","..................O...............................","..................O...............................","..................O...............................","..................O...............................","..................O...............................","..................OOOOOOOOOOOOOOOOO...............","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................","..................................................",".................................................."}

    {"W 9","W 7","N 6","N 6"}

    Returns: { 18, 22 }

  17. {"OOXOOOO"}

    {"W 2"}

    Returns: { 2, 0 }

  18. {"...........O............................","..........OOOO..........................","..........OOO.....O....O................","...........OO....OOOOO.OO...............",".........OOO...OOOOOOO.OOOO....O........",".........OOOO...OOOOOO.OOOOOOOOO........","...........O..OOOOOOOOOOOOOOOOOOO.......","..........OOOOOOOOOOOOOOOOOOOOOO........",".......OOOOOOOOOOOOOOOOOOOO.O..O........","........OOOOOOOOOOOOOOOOOO..............","......OOO.OOOOOOOOXOOOOOOOOO............","...........OOOOOOOOOOOOOOOOO.OO.........","...........OOOOOOOOOOOOOOOOOOOOO........","............OOOOOOOOOOOOOOOOOOOO........","...........OOOOOOOOOOOOOOOOOOOOOO.......","............OOOOOOOOOOOOOOOOOOOOO.......",".............OOOOOOOOOOOOOOOOOOO........","...........OOOOOOOOOOOOOOOOOOOOO........","..........OOOOOOOOOOOOOOOOOOOOO.........","..........OOOOOOOOOOOOOOOOOOOOO.........","..........OOOOOOOOOOOOOOOOOOOOOOO.......","...........OOOOOOOOOOOOOOOOOOOOO........","............OOOOOOOOOOOOO.O.OOO.........",".............OOOOOOOOOOOO...OOOO........",".............OOOOOOOOOO...OOO.O.........","..............OOOOOOO.....O...OOO.......",".............OOOO.........OO..O.O.......","...............O...........O....O......."}

    {"N 4","E 2","S 1","W 3","N 2","W 1","E 1","N 3","S 2","W 1","N 3","W 1","S 4"}

    Returns: { 22, 16 }

  19. {"...","OOX"}

    {"E 1","N 1","S 1","E 1"}

    Returns: { }

  20. {"OOX"}

    {"E 1","N 1","S 1","E 1"}

    Returns: { }

  21. {"..O.OOOOO","..OOO...O","..O.....O","O.O.....X","OOO......"}

    {"S 1","E 2","N 1"}

    Returns: { 4, 0 }

  22. {".O.O.O.O.O.O.O.O.O.O.O.O.X.O.O.O.O.O.O.O.O.O.O.O..",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O",".O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O","OO.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O.O","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO"}

    {"S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","N 1","S 1","E 1"}

    Returns: { 24, 49 }

  23. {"OO","X.","OO"}

    {"W 1"}

    Returns: { 0, 0 }

  24. {"OXO","O.O"}

    {"N 1"}

    Returns: { 0, 0 }

  25. {"OO",".X","OO"}

    {"E 1"}

    Returns: { 1, 0 }

  26. {"O.O","OXO"}

    {"S 1"}

    Returns: { 0, 1 }

  27. {"OOOOO","OXOOO","OOOOO",".O.O."}

    {"N 1"}

    Returns: { 0, 1 }

  28. {"XOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO","OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO"}

    {"W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9","W 9","E 9"}

    Returns: { 9, 0 }

  29. { "OOOOO", "OOX.O", "OOO.O" }

    { "N 1", "W 2" }

    Returns: { 2, 0 }

  30. { "OX" }

    { "E 1" }

    Returns: { 1, 0 }

  31. { "O", "O", "X" }

    { "N 1", "S 1" }

    Returns: { 0, 2 }

  32. { "OOOOX", "O....", "OOOOO" }

    { "N 2" }

    Returns: { 0, 0 }

  33. { "OOO", "OXO", "OOO" }

    { "N 1" }

    Returns: { 1, 1 }

  34. { ".......", ".OOOOO.", ".OOOOO.", ".OOXOO.", ".OOOOO.", ".OOOOO.", "......." }

    { "N 1" }

    Returns: { 3, 4 }

  35. { "OOOOO", "OOOOO", "OOXOO", "OOOOO", "OOOOO" }

    { "N 1" }

    Returns: { 2, 3 }

  36. { "OOO", "OOO", "OOX" }

    { "E 2" }

    Returns: { 2, 2 }

  37. { "O", "X", "O" }

    { "N 1", "S 1" }

    Returns: { 0, 1 }

  38. { ".OOO", "OOOO", "OOXO", "OOOO" }

    { "E 1", "S 1" }

    Returns: { 2, 1 }

  39. { "OX" }

    { "W 1", "E 1" }

    Returns: { 1, 0 }

  40. { ".OOO", "OX.O", "...." }

    { "W 2" }

    Returns: { 1, 0 }

  41. { "OX" }

    { "E 9" }

    Returns: { }

  42. { ".X.", "OOO", ".O." }

    { "N 1" }

    Returns: { 1, 1 }

  43. { ".....", ".XOO.", ".OOO.", ".OOO.", "....." }

    { "S 1", "E 1", "N 1", "W 1" }

    Returns: { 1, 1 }

  44. { ".OO", "OOX", "OOO" }

    { "E 1" }

    Returns: { 2, 0 }

  45. { ".O.", "OOO", "OXO" }

    { "S 1" }

    Returns: { 1, 1 }

  46. { "O.X", "OOO" }

    { "E 2" }

    Returns: { 2, 1 }

  47. { ".O.", "OOX", ".O." }

    { "E 1" }

    Returns: { 1, 1 }

  48. { "OO.", "OXO", ".OO" }

    { "E 1", "S 1" }

    Returns: { 1, 1 }

  49. { ".OOO", "OOXO", "OOOO" }

    { "E 1" }

    Returns: { 2, 0 }

  50. { "X.O", "OOO" }

    { "E 2", "S 1" }

    Returns: { }

  51. { "OXO", "OOO", "OOO" }

    { "S 1", "N 1" }

    Returns: { 1, 0 }

  52. { ".OO", "OOO", "OXO" }

    { "S 1" }

    Returns: { 1, 1 }

  53. { "..", "XO" }

    { "E 1", "W 1" }

    Returns: { 0, 1 }

  54. { "OXO", "OOO", ".O.", ".O." }

    { "N 1" }

    Returns: { 0, 0 }

  55. { "..OOOOOOOOOOOOOO", "..OOOOOOOOOOOOOO", "..OOOOOOOOOOOOOO", "..OOOOOOOOOOOOOO", "..OOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOO", "OOOOOOOOOOOOOOOO", "OOOOOOOOOOOOXOOO" }

    { "W 1", "E 1", "S 1" }

    Returns: { 15, 11 }

  56. { "..........", "......O...", "...O.OO...", "...OOOO...", "...OXOO...", "...OOOO...", "...O.O....", ".........." }

    { "S 4" }

    Returns: { 6, 5 }

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: