Please write a full answer, do not answer it if you do not know it!

8. Snakes and Ladders is a classic board game, originating in India no later than the 16th century. The board consists of an n x n grid of squares, numbered consecutively from 1 to n*, starting in the bottom left corner and proceeding row by row from bottom to top, with rows alternating to the left and right. Certain pairs of squares in this grid, always in different rows, are connected by either "snakes" (leading down) or "ladders" (leading up). Each square can be an endpoint of at most one snake or ladder. 100 99 98 97 96 95 94 93 92 91 81 82 83 84 85 86 74 73 271 68 69 70 78 77 76 65 66 60 41 42 43 44 40 39 38 37 36 35 34 3332 31 21 22 23 20 19 18 1716 55 54 46 8 29 30 7 A typical Snakes and Ladders board Upward straight arrows are ladders; downward wavy arrows are snakes You start with a token in cell 1, in the bottom left corner. In each move, you advance your token up to k positions, for some fixed constant k. If the token ends the move at the top end of a snake, it slides down to the bottom of that snake. Similarly, if the token ends the move at the bottom end of a ladder, it climbs up to the top of that ladder. Describe and analyze an algorithm to compute the smallest number of moves required for the token to reach the last square of the grid 8. Snakes and Ladders is a classic board game, originating in India no later than the 16th century. The board consists of an n x n grid of squares, numbered consecutively from 1 to n*, starting in the bottom left corner and proceeding row by row from bottom to top, with rows alternating to the left and right. Certain pairs of squares in this grid, always in different rows, are connected by either "snakes" (leading down) or "ladders" (leading up). Each square can be an endpoint of at most one snake or ladder. 100 99 98 97 96 95 94 93 92 91 81 82 83 84 85 86 74 73 271 68 69 70 78 77 76 65 66 60 41 42 43 44 40 39 38 37 36 35 34 3332 31 21 22 23 20 19 18 1716 55 54 46 8 29 30 7 A typical Snakes and Ladders board Upward straight arrows are ladders; downward wavy arrows are snakes You start with a token in cell 1, in the bottom left corner. In each move, you advance your token up to k positions, for some fixed constant k. If the token ends the move at the top end of a snake, it slides down to the bottom of that snake. Similarly, if the token ends the move at the bottom end of a ladder, it climbs up to the top of that ladder. Describe and analyze an algorithm to compute the smallest number of moves required for the token to reach the last square of the grid