Snakes and Ladders is the new hit game at the Computer Science Games night. Intent on being the all time champion, you invest in a rigged die which allows you to roll whatever outcome you please. You quickly realize that the greedy approach of rolling a 6 each turn may not be the best strategy as you may miss advantageous ladders, or find yourself constantly sliding down those pesky snakes (not to mention rolling the same number every turn basically broadcasts to everyone that you are cheating). Given a snakes and ladders game board, determine the tile sequence of the optimal solution.
For those of you unfamiliar with the game, the rules are as follows:
Each turn a player rolls a single die labeled with numbers 1-6, receiving and outcome of N. Starting at
tile 1, the player advances N tiles forward. If the resulting tile is a ladder tile, the player must fully climb the ladder. If the resulting tile is a snake, the player slides down. The player who reaches tile 100 first is the winner.
For example, given the above depicted game board if the player lands on tile 4, they will climb the ladder and end the turn on tile 14. In contrast, if the player lands on tile 62 they will descend the snake and end the turn on tile 19.
An integer N denoting the number of special tiles (snakes or ladders)
N pairs of space separated integers denoting the start and end of the special tiles
Space separated integers denoting the sequence of tiles in an optimal solution. If more than one such sequence exists, just output one of them.