(Hacker Rank) Snakes and Ladders: The Quickest Way Up - Solution

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

The problem asks to find the shortest path from one specific position to another one. However, it does not have any weight associated to the edges, which suggests that the algorithm to be used here is the Breadth-First Search (BFS).


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static HashMap<Integer, ArrayList<Integer>> adjList;
    public static HashSet<Integer> startingPoints;
    public static int[] dice = {1,2,3,4,5,6};
   
    public static int bfs(int start, int end) {
        Queue<Move> queue = new ArrayDeque<Move>();
        queue.add(new Move(start, 0));
       
        HashSet<Integer> visited = new HashSet<Integer>();
       
        while (queue.size() > 0) {
            Move curr = queue.poll();
            int currPos = curr.pos;
            int currCount = curr.count;
           
            if (visited.contains(currPos)) {
                continue;
            }
            visited.add(currPos);
           
            if (currPos == end) {
                return currCount;
            }
           
            ArrayList<Integer> reachPos = adjList.get(currPos);
            for (int i = 0; i < reachPos.size(); i++) {
                int count = currCount;
                if (!startingPoints.contains(reachPos.get(i))) {
                    count++;
                }
                queue.add(new Move(reachPos.get(i), count));
            }
        }
       
        return -1;
    }
   
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            adjList = new HashMap<Integer, ArrayList<Integer>>();
            for (int j = 1; j <= 100; j++) {
                adjList.put(j, new ArrayList<Integer>());
            }
           
            startingPoints = new HashSet<Integer>();
            int numLadders = sc.nextInt();
            for (int j = 0; j < numLadders; j++) {
                int startingPoint = sc.nextInt();
                int endingPoint = sc.nextInt();
                adjList.get(startingPoint).add(endingPoint);
                startingPoints.add(startingPoint);
            }
            int numSnakes = sc.nextInt();
            for (int j = 0; j < numSnakes; j++) {
                int startingPoint = sc.nextInt();
                int endingPoint = sc.nextInt();
                adjList.get(startingPoint).add(endingPoint);
                startingPoints.add(startingPoint);
            }
           
            for (int j = 1; j <= 100; j++) {
                if (adjList.get(j).size() == 1) {
                    continue;
                }
                for (int k = 0; k < 6; k++) {
                    int nextPos = j+dice[k];
                    if (nextPos <= 100) {
                        adjList.get(j).add(nextPos);
                    }
                }
            }
           
            System.out.println(bfs(1, 100));
           
        }
    }
}

class Move {
    int pos;
    int count;
   
    public Move(int p, int c) {
        pos = p;
        count = c;
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução