Programming Assignment # 8 Due 11pm Wednesday, Mar 18 CS 130A Data Struc & Alg 1 Submit via Gradescope Snakes and Ladders : Graphs For this assignment, we are going to play Snakes and Ladders, a classic board game. Essentially, it is a 10×10 board game as shown below In this game, a die is rolled in every move by a player. The number obtained from your die roll decides how much further you can move your player on the board in a that move. The aim is to reach position 100 from position 1, in the least amount of moves, beating any other player around. Now, if you get to a position which has a ladder starting from there, you take the ladder and move up in that move itself. But if you land in a position where there is a snake head, you are pulled down to where the snake tail ends. There is no way to climb down a ladder or to go up through a snake. That is all that we need to know for this problem. If you want to read more about it, have a look here, http://en.wikipedia.org/wiki/Snakes_and_Ladders. For this assignment, you have to consider the general NxN board game, with N ranging from 5 to 100. Now suppose, you are the awesome Magneto and you are trying to solve this game in the least number of moves (as if you are bored and don’t have anything else to do other than solving a silly human game). As Magneto, you can control gravity and thereby control whatever number the die can show when it is rolled. Now that we have got that part figured out and have got the uncertainity of a random die roll out of the game, you are tasked figuring out a way to compute the die rolls that you need to make in order to win the game in the least number of moves, given any NxN board. 1 Input Input will be of the following format. The first line will have a number T, which is the number of board games, which need to be solved. The next 3T lines will contain more information about the boards, 3 lines per board. The first of the 3 lines will have three numbers, N, L, S. Here, N is the board size. L and S are the number of ladders and snakes on the boards respectively. The second line will 2L numbers, where each consecutive pair a, b represents the starting and ending points of a ladder respectively. The third line will have 2S numbers, where each consecutive pair c, d represents the head and tail of a snake respectively. Output Output will be of the following format, consisting of 3T lines, 3 per board. The first of these lines have a text like Board Game #i, which i is the number of the board game currently being solved. The next line will also have a single number, M, the least number of moves required for solving the current board. The next line should show the path taken with ladders shown as + and snakes as -. Sample Input 5 8 1 1 8 11 63 1 10 3 7 32 62 42 68 12 98 95 13 97 25 93 37 79 27 75 19 49 47 67 17 10 6 8 32 62 44 66 22 58 34 60 2 70 71 87 85 7 63 31 87 13 75 11 89 33 57 5 71 15 55 25 20 10 11 8 52 371 389 313 351 6 80 26 42 2 72 80 147 124 301 2 99 90 107 51 19 39 11 37 29 81 3 59 5 79 23 53 7 43 33 77 21 207 3 378 78 60 3 2 2 131 119 3555 1563 2013 140 117 3402 234 Sample Output Board Game #1: 11 1 7 13 19 25 31 37 43 49 55 61 64 Board Game #2: 3 1 7 12+98 100 Board Game #3: 6 1 2+70 76 82 88 94 100 2 Board Game #4: 14 1 2+99 105 111 117 123 124+301 307 313+351 357 363 369 371+389 395 400 Board Game #5: 12 1 2+131 137 140-117 119+3555 3561 3567 3573 3579 3585 3591 3597 3600 Note It’s possible for multiple solutions to exist for a given step cost. For example, both the following two results are valid for Board Game #1. Board Game #1: 11 1 7 13 19 25 31 37 43 49 55 59 64 Board Game #1: 11 1 7 13 19 25 31 37 43 49 55 61 64 You should output the one that makes largest leap at every possible step from left to right. Therefore, the correct output is the following one: Board Game #1: 11 1 7 13 19 25 31 37 43 49 55 61 64 General Issues The TAs should be able to run your implementation as “./snl” with input from argv[1] just like in PA1. Be sure to include a Makefile, and name the executable as described. The program should be able to terminate after processing all requisite input, as predicted by T, the number of board games. The programs are tested automatically so make sure that you provide the output exactly as specified and shown above with no extra space lines to the output. The program should output to stdout. The input provided above is the subset of the input your program would be tested against. So be sure to check your program exhaustively for different cases. This programming assignment is to be implemented in C++. Submission You need to submit all the files having your implementation and the Makefile. 3
