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