(Hackerrank) Snakes and Ladders: The Quickest Way Up

Found this problem in graph theory section of hackerrank and had so much fun solving it 🙂

             https://www.hackerrank.com/challenges/the-quickest-way-up

Its about finding the least number of rolls of the die in which one can able to reach the destination square (Square Number 100) after having started at the base square (Square Number 1) provided one has the power to get any number (1-6) on the die when one rolls it.

 Solution :

Connect vertex i with i+1,i+2,i+3,i+4,i+5,i+6 ( denoting that from square i you can move to square i+1(when you get 1 when rolling the die),i+2(when you get 2 when rolling the die) and so on)

Similarly consider the starting and ending square of ladder , starting and ending square of the snake as vertices in the graph considered

Apply Floyd warshall algorithm and find minimum distance between square 1 to 100.