This Week's Problem

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.

Input Format

  • 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

Output Format

  • Space separated integers denoting the sequence of tiles in an optimal solution. If more than one such sequence exists, just output one of them.

Sample Input

32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17

Sample Output

1 7 98 100
3rd and 4th year student solutions must use an informed search algorithm such as A*.