**Objective** – Given a snake and ladder game, write a function that returns the minimum number of jumps to take top or destination position.

You can assume the dice you throw results in always favor of you means you can control the dice.

**Rules**:

- Start from cell 1.
- Throw the dice and whatever number you get, move on the number of cells on the board.
- If you reach a cell which is base of a ladder, then you have to climb up that ladder without a dice throw.
- If you reach a cell is mouth of the snake, has to go down to the tail of snake without a dice throw.

**Example**:

Minimum moves required to reach end (36^{th} cell) from start(1^{st} cell) = 3

- First throw on dice, get 2 to reach cell number 3, then take the ladder to reach 16.
- Second throw on dice to get 5 to cell number 21, and then take ladder to reach 32.
- Third throw on dice to get 4 to reach cell number 36.

**Approach**:

- Consider each as a vertex in directed graph.
- From cell 1 you can go to cells 2, 3, 4, 5, 6, 7 so vertex 1 will have directed edge towards vertex 2, vertex 3….vertex 7. Similarly consider this for rest of the cells.
- For snake- connect directed edge from head of snake vertex to tail of snake vertex. (See example image above- snake from 12 to 2. So directed edge from vertex 12 to vertex 2)
- For ladder- connect directed edge from bottom of ladder vertex to top of the ladder vertex.
- Now problem is reduced to Shorted path problem. So by Breadth-First Search (using queue) we can solve the problem.

**Implementation**:

- Each vertex will store 2 information, cell number and number of moves required to reach to that cell. (cell, moves)
- Start from cell (vertex) 1, add it to the queue.
- For any index = i, Remove vertex ‘i’ from queue and add all the vertices to which can be reached from vertex ‘i’ by throwing the dice once and update the moves for each vertex (moves = moves to reach cell ‘i’ + 1 if no snake or ladder is present else moves = cell to which snake or ladder will leads to)
- Remove a vertex from queue and follow the previous step.
- Maintain visited[] array to avoid going in loops.
- Once reach to the end(destination vertex), stop.

See the animation below for more understanding.

**Time Complexity: O(N)**

**Complete Code**:

import java.util.LinkedList; | |

import java.util.Queue; | |

public class SnakeAndLadder { | |

static class Vertex { | |

int cell; | |

int moves; | |

} | |

public int findMinMoves(int [] board){ | |

int size = board.length; | |

//create visited array for each cell | |

boolean [] visited = new boolean[size]; | |

Queue<Vertex> queue = new LinkedList<>(); | |

//start from position 1 (index 0) and it is already visited | |

Vertex vertex = new Vertex(); | |

vertex.cell=0; | |

vertex.moves =0; | |

queue.add(vertex); | |

visited[0] = true; | |

//BFS from cell number 0 | |

while(queue.isEmpty()==false){ | |

//remove from front of queue | |

vertex = queue.remove(); | |

int cellNum = vertex.cell; | |

//check if reached to the end | |

if(cellNum==size–1) | |

break; | |

//if not reached to the end then add the reachable adjacent cells from the current cells | |

//Since dice can be controlled and max value can be achieved 6 | |

//so from the current cell, you can reach to next 6 cells so add next 6 cells | |

for (int i = cellNum+1; i <(cellNum+6) && i<size ; i++) { | |

//check if cell is already not visited | |

if(visited[i]!=true){ | |

//add it to the queue, update moves and mak visited | |

Vertex currentVertex = new Vertex(); | |

currentVertex.moves = vertex.moves+1; //can be reached by throwing dice one more time | |

visited[i] = true; | |

//now fill the cell can be reached (might be snake or ladder) | |

if(board[i]==–1){ | |

//means can be reached by throwing dice at that cell | |

currentVertex.cell = i; | |

}else{ | |

//might be snake OR ladder at this cell 'i' | |

//then tail of the snake or top of the ladder will be achieved | |

// by reaching at cell 'i' | |

currentVertex.cell = board[i]; | |

} | |

//add to queue | |

queue.add(currentVertex); | |

} | |

} | |

} | |

return vertex.moves; | |

} | |

public static void main(String[] args) { | |

int size = 36; | |

int [] board = new int[size]; | |

for (int i = 0; i <size ; i++) { | |

board[i] = –1; | |

} | |

//ladders | |

board[2] = 15; | |

board[14] = 24; | |

board[20] = 31; | |

// Snakes | |

board[11] = 1; | |

board[29] = 3; | |

board[34] = 21; | |

SnakeAndLadder s = new SnakeAndLadder(); | |

System.out.println("Minimum Dice throws needed to reach to end: " + s.findMinMoves(board)); | |

} | |

} |

**Output**:

Minimum Dice throws needed to reach to end: 3

Reference: here