## Introduction

For those who are not familiar with the snakes and ladders game. Here is a link for introduction. So the fastest reach in snakes and ladders, is a modified version of the game. So, you are playing the game called snakes and ladders and you have an enchanted dice. You are the master of the dice and you can command it to get any number between 1 and 6 both inclusive. This means that when you throw the dice, the number on the upper face is totally controlled by you. If you ask for a 5, you get a 5 and so on.## Problem Statement - Fastest Reach in Snakes and Ladders

The problem in hand is to find the minimum number of steps you will need to reach the cell labelled 100. The board given to you will have positions of ladders and snakes as follows: L = 3 - [8, 77], [37, 94], [58, 82] S = 5 - [99, 12], [87, 57], [72, 30], [90, 43], [53, 2] The above data suggests that we have 3 blue ladders, the first one starts from cell 8 and takes you to the cell 77. The second one starts from cell 37 and takes you to cell 94 and so on. Similarly, there are 5 red snakes and if you land up on cell 99, the snake will bite you and you will end up on cell 12.## Approaching the problem

The problem is on the similar lines as Single Source Shortest Path. In this problem we are expecting to find the shortest path given a directed graph. The vertices of the graph are cells and the edges are possible paths from one cell to another. Possible new paths or edges are result of ladders and snakes on the board. Each vertex will have 6 outgoing edges. For e.g.: If you are at cell 1, you can choose to move to cell 2, 3, 4, 5, 6 or 7 by getting a number between 1-6 from the dice. This means that it takes just one turn to move from 1 to any of the next 6 cells. The condition becomes interesting when there is a ladder. Consider that you are at cell 4. You can move to 5, 6, 7, 8, 9 or 10 by getting a number between 1 and 6 from the dice. But the moment you land on 8, by the property of the ladder you will reach 77. Hence, to reach 77 from cell 4 you will just need 1 turn.### Storing the Graph

The graph has to be stored in a way such that the operations on it for the given problem can be easily done. In this case, we just need to store the ladders and snakes, because rest all the cells (vertices) and paths (edge) are fixed. For e.g.: we know that from each cell there are 6 outgoing edges to the next 6 consecutive cells. The only information which varies is the edges created by the snakes and the ladders. Hence, we will store the information in a board. The board is a one dimensional zero indexed array of length 100. We will initialize the complete array with -1, just to mark that there are no snakes and ladders yet. Then as we get ladders and snakes we update the array. The array stores the destination of each ladder and snake. For e.g. the ladder which starts at 8 and ends at 77 can be stored as the value (77-1) at the index (8-1). So index 7 contains the value 76 (this is due to the zero based indexes).### Algorithm to solve fastest reach in snakes and ladders

Here is a simple algorithm which will work, the motivation for it is the breadth first search- Start from the first cell, add it in a queue. The distance/ number of turns to reach this cell is zero.
- Remove the first cell from the queue and update the distances of next 6 cells to 1. This is because, you can reach to any of the six cells from the first cell, in one turn.
- Add all these 6 cells in the queue. Mark these cells as visited.
- Remove the cells from the queue one by one and follow the above procedure.
- Every time you visit an un-visited cell, update it distance as 1 + the distance to the current cell.
- When the final cell (100) is removed from the queue, the algorithm is over. The distance of cell 100 is the answer to the problem