New to Graph theory and the link helped me solve this. Took me a while but it was well worth it! :)

I definately will look into it. I solved it with a markov chain, it seemed apropriate... or maybe the name in the problem statement misleaded me :3

In that link:

"... He assume that getting caught by a snake is always unfavorable, and will not add to the progress of a short path..."

That is false. Is easy find an example.

"getting caught by a snake is always unfavorable, and will not add to the progress of a short path"

This does not seem to be accurate. Suppose a ladder is from 2 to 82, a snake is from 84 to 62 and another ladder is from 62 to 99 and nothing else, the optimal solution is to take the ladder to 82, then the snake from 84 to 62 and then take the ladder from 62 to 99.

Thanks for the awesome link!!!

Thank you so much for this link. It gaves me correct way to solve this, with C# using BFS (level by level search) :my first Graph

Thanks for the wonderful link. Here is my solution in java entirely based on the idea provied in the link

import java.io.; import java.util.;

public class QuickestWayUpLadder { private static byte MAX_ROLL = 6; private static byte BOARD_LEN = 100; private static Map> adjencyMap=new HashMap>(); private static Map listSnakes=new HashMap(); private static Map listLadders=new HashMap();

public static void main(String[] args) throws IOException { final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

//Create board
final byte[] board = new byte[BOARD_LEN];

//For every test case
for(byte T = Byte.parseByte(br.readLine()); T > 0; --T){

  //Initialize board
  for(byte i = 0; i < BOARD_LEN; ++i){
    board[i] = i;
  }

  //Get ladder
  for(byte N = Byte.parseByte(br.readLine()); N > 0; --N){
    final String[] line = br.readLine().split(" ");
    final byte S = (byte)(Byte.parseByte(line[0]) - 1);
    final byte E = (byte)(Byte.parseByte(line[1]) - 1);
    listLadders.put(S,E);
  }

  //Get snakes
  for(byte M = Byte.parseByte(br.readLine()); M > 0; --M){
    final String[] line = br.readLine().split(" ");
    final byte S = (byte)(Byte.parseByte(line[0]) - 1);
    final byte E = (byte)(Byte.parseByte(line[1]) - 1);
    listSnakes.put(S,E);
  }
  System.out.println();
  for(byte i = 0; i < BOARD_LEN; ++i){
      System.out.print(board[i]+" ");
    }

  createAdjacencyList(board);
  replace();
  printAdjencyList();

  breathFirstSearch();
  //Solve and print output

// System.out.println(getMinMoves(board)); } }

private static void createAdjacencyList(byte[] board){

   for(byte i=0;i<board.length;i++){

       for(byte j=0;j<7;j++){
         if(i+j>99)
             break;
           if(adjencyMap.containsKey(board[i]))
            adjencyMap.get(board[i]).add(board[i+j]);
           else
            adjencyMap.put(board[i],new ArrayList(board[i+j]));
       }
   }

}

private static void printAdjencyList(){ for(byte i :adjencyMap.keySet()){ System.out.println(); System.out.print("key: "+i+"values: "); for(byte temp: adjencyMap.get(i)) { System.out.print(temp+" "); } } }

private static void replace(){ for(Byte t: adjencyMap.keySet()){ List temp=new ArrayList();

       for(Byte t1: adjencyMap.get(t))
   {

       if(listLadders.containsKey(t1)){
            temp.add(listLadders.get(t1));
       }
       else if(listSnakes.containsKey(t1)){
        temp.add(listSnakes.get(t1));
       }
       else
       temp.add(t1);
   }

   adjencyMap.put(t,temp);
   }

}

private static void breathFirstSearch(){ int count=0; byte i=0; while(i!=99){ List temp=adjencyMap.get(i); Collections.sort(temp); i=temp.get(temp.size()-1); count++; if(i>99) break; } System.out.println(); System.out.println("number of steps: "+count); } }

Thanks man, for the link it was really helpfull

Solved using Dijkshtra algorithm :D

import java.util.*;
import java.io.*;
public class Solution {
	    public static void main(String[] args){
	  Scanner in=new Scanner(System.in);
	  int test=in.nextInt();
	  for(int h=0;h<test;h++){
	  int w[][]=new int[101][101];
      for(int i=1;i<=100;i++){
      	for(int j=1;j<=100;j++){
      		if(i!=j &&i<j && Math.abs(j-i)<=6){
      			w[i][j]=1;
      		}
      		else{w[i][j]=1000000;}
      	}}
      int ladder=in.nextInt();
      for(int i=0;i<ladder;i++){
    	  int x=in.nextInt(),y=in.nextInt();
        	w[x][y]=0;
      }
      int snake=in.nextInt();
      int sn[]=new int[snake];
      for(int i=0;i<snake;i++){
    	  int x=in.nextInt(),y=in.nextInt();sn[i]=x;
    	w[x][y]=0;
      }
      Arrays.sort(sn);int cnt=0;
      for(int g=0;g<snake;g++){if(g>0 && sn[g]-sn[g-1]==1){++cnt;}else{cnt=0;}if(cnt>=6){break;}}
	   Stack <Integer> t=new Stack<Integer>();
          int src=1,des=100;
        for(int i=1;i<=100;i++){
        	if(i!=src){t.push(i);}}
        Stack <Integer> p=new Stack<Integer>();
        p.push(src);
          while(!t.isEmpty()){int min=989997979,loc=-1;
        for(int i=0;i<t.size();i++){
        	w[src][t.elementAt(i)]=Math.min(w[src][t.elementAt(i)],w[src][p.peek()]+w[p.peek()][t.elementAt(i)]);
            if(w[src][t.elementAt(i)]<=min){
            	min=(int) w[src][t.elementAt(i)];loc=i;}
        }
        
        p.push(t.elementAt(loc));t.removeElementAt(loc);}
           if(cnt>=6){System.out.println("-1");continue;}
        	 if(w[src][des]!=1000000){System.out.println(w[src][des]);}
        	 else {System.out.println("-1");}
        
  }}}

Thanks a lot for this link with amazing explanation!

helpful link...gives an exact idea ..all u need is the implementation of the code and finding distance using bfs.

Thanks For the Link Sir, really helped me to undersatnd the concept.

really appreacited. All I understand how well you make the adj list. Just implememt bfs and "BINGO".

f(i,100){ if(snakes[i] or ladders[i]) continue; f1(j,1,7){ if(ladders[i+j] != 0){ adj[i].pb(ladders[i+j]); } else if(snakes[i+j] != 0 ){ adj[i].pb(snakes[i+j]); } else { adj[i].pb(i+j); } } } bfs(1);

I think using adjacency matrix is easier than using adjacency list due to relative easy of changing the updating the nodes for ladders and snakes.

Your comment is very much helpful. Thankew very much

Thanks for this - I was going to go Dijkstra, but it felt a little heavy for a graph with equal edge costs. I wouldn't have thought of BFS, and needed to think of how to apply it, but doing so gave me an addition to the toolbox!

This comment actually made more sense to me. Especially your last paragraph. I'm new to graph problems, I understand BFS and DFS, but I didn't know how to approach the whole die rolls. The key in the BFS is to enqueue its adjacent nodes based on the max die roll value which is 6 (Could be 12 if using two dice), but you need to watch out for snakes while doing it. Also for me I checked if there were 6 consecutive Nodes with a snake head and if I found that true I return -1, I did this before the BFS no need to do a BFS if there is no possible solution.

Most useful hint! Thanks!

here's a simple java solution that does it according to your description

import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Queue;

class Solution{
    static final int squares=100;
    static final int nowhere=-1;
    static int solve(int[] trans){
	boolean[] vis=new boolean[squares];
	Queue<Integer> q=new ArrayDeque<Integer>();
	final int start=0,dice=6,noSolution=-1,win=squares-1;
	q.add(start);
	vis[start]=true;
	int[] roll=new int[squares];
	// q never contains spot with start of snake/ladder
	while(!q.isEmpty()){
	    int x=q.poll();
	    for(int i=1;i<=dice && x+i<squares;++i){
		int j=x+i;
		while(!vis[j]){
		    vis[j]=true;
		    if(j==win) return roll[x]+1;
		    else if(trans[j]==nowhere){
			q.add(j);
			roll[j]=roll[x]+1;
		    }
		    else j=trans[j];
		}
	    }
	}
	return noSolution;
    }
    static int[] transport(int[][] ladder, int[][] snake){
	int[] tr=new int[squares];
	for(int i=0;i<squares;++i) tr[i]=nowhere;
	for(int[] l: ladder) tr[l[0]]=l[1];
	for(int[] s: snake) tr[s[0]]=s[1];
	return tr;
    }
    static int[][] readEdge(int n, Scanner sc){
	int[][] edge=new int[n][2];
	for(int i=0;i<n;++i){
	    edge[i][0]=sc.nextInt()-1;
	    edge[i][1]=sc.nextInt()-1;
	}
	return edge;
    }
    static void input(){
	Scanner sc=new Scanner(System.in);
	int t=sc.nextInt();
	for(int i=0;i<t;++i){
	    int n=sc.nextInt();
	    int[][] ladder=readEdge(n,sc);
	    int m=sc.nextInt();
	    int[][] snake=readEdge(m,sc);
	    int[] trans=transport(ladder,snake);
	    System.out.println(solve(trans));
	}
	sc.close();
    }
    public static void main(String[] args){
	input();
    }
}

Thanks for the explanation!

For python3, i have used next starter before BFS cycle:

visited = set()
queue = []
ladders = {i:j for i,j in ladders}
snakes = {i:j for i,j in snakes}
queue.append((1,0))

updated :)

Agreed. I feel like if we have to spend time reading an external link, it should be a cool algorithm not the rules for a game.