Problem Statement
You love to play a solitare game on your computer which uses Mahjong tiles (little rectangular tiles with various symbols on them). The object is to remove all the tiles from the board. Tiles are removed in matching pairs. Only tiles which are "open" can be removed. A tile is not open if it has neighbors to both its immediate right and to its immediate left. If either or both of the neighbors are missing, then the tile is open. Being on the left or right edge of the playing board is also considered open. To remove a pair of tiles, you move your cursor to the center of one tile and click. Next you move your cursor to the center of the matching tile and click there. The two tiles are then removed by the game.
You are very good at playing this game so you are not worried so much about just winning. You now try to win the most efficient way possible. Your task in this problem is to find a sequence of moves which wins the game, and has the cursor follow the shortest possible path while doing so. You may start at any tile. Return the length of the shortest winning path. For simplicity, the cursor paths will be measured between the exact tile centers. If there is no winning sequence (some tiles are unplayable) return -1.
For example on the board below: (where a blank cell on the board is represented by the character '.' and tiles are upper case letters)
"..A.E" ".BCA." "BCDED"
The topmost "A" and "E" tiles are open (free on both sides). The "B" and "A" tiles on the second row are open (free on one side). The "C" tile in the middle is not open. The outside "B" and "D" tiles on the bottom row are open, while the middle "C","D", and "E" tiles are not open. From this position your available moves are to remove a pair of "A" tiles or a pair of "B" tiles. The "C","D", and "E" tiles may not be played on this move, since there is not a matching pair of those tiles with both tiles open.
One sequence of moves is to remove the two "B" tiles first. This frees both "C" tiles so they now may be played. Removing the two "C" tiles frees one of the "D" tiles (the other was already free). Then removing the two "D" tiles frees the last non-free tile, an "E" (the other "E" is already free). Then the two "E" tiles can be removed, and the two "A" tiles can be removed, emptying the board. This description of the moves is incomplete (for this problem) because which tile of each pair was "clicked" first is significant for the distance calculation. This particular sequence of moves is not optimal. See the examples for a complete specification of an optimal sequence for this position.
Definition
- Class:
- MahjongTiles
- Method:
- shortestPath
- Parameters:
- String[]
- Returns:
- double
- Method signature:
- double shortestPath(String[] board)
- (be sure your method is public)
Notes
- Your answer must be within 1.0e-9 (absolute or relative) of the reference answer.
Constraints
- board will have between 1 and 16 elements inclusive.
- Each element of board will have between 1 and 36 characters inclusive.
- Each element of board will have the same number of characters.
- There will be between 2 and 16 tiles in the board.
- Only the characters "ABCDEFGH" and "." will appear in board (quotes for clarity only)
- Each tile character ("A" to "H") can be present on the board exactly 0, 2, or 4 times, thus the total number of tiles must also be even.
Examples
{"..A.E", ".BCA.", "BCDED"}Returns: 12.892922226992171
This is the example from above. A minimum length winning path starts at the "B" in the lower left and goes up and to the right sqrt(2) "B", up and to the right sqrt(2) to "A", then down and right sqrt(2) to "A", left 1 to "C", down and left sqrt(2) to "C", right 1 to "D", right 2 to "D", left 1 to "E", and up and right sqrt(5) to "E". 4*sqrt(2)+5+sqrt(5)=12.89292222699217{"AA.BB.CC.EE", "AA.BB.CC.EE"}Returns: 18.0
{".AADABA....BCDC..."}Returns: 38.0
{"....ABCDEABCDE...."}Returns: -1.0
{"A.B.C.D.E.H.F.G..........", "..........A.E.B.D.C.F.G.H"}Returns: 91.46030463848523
Back to all problems