SnakeLadder.java

package learnings;

import java.util.*;

// Data structure to store graph edges
class Edge {
    int src, dest;
    public Edge(int src, int dest) {
        this.src = src;
        this.dest = dest;
    }
}

// A queue node
class Node {
    // stores number associated with graph node
    int ver;

    // minDist stores minimum distance of node from starting vertex
    int minDist;

    public Node(int ver, int minDist) {
        this.ver = ver;
        this.minDist = minDist;
    }
}

// class to represent a graph object
class Graph {
    // An array of Lists to represent adjacency list
    List<List<Integer>> adjList = null;

    // Constructor
    Graph(List<Edge> edges, int N) {
        adjList = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            adjList.add(i, new ArrayList<>());
        }

        // add edges to the graph
        for (int i = 0; i < edges.size(); i++)
        {
            int src = edges.get(i).src;
            int dest = edges.get(i).dest;

            // Please note that directed is directed
            adjList.get(src).add(dest);
        }
    }
}

class SnakeLadder {
    // Perform DFS on graph g starting from given source vertex
    public static void BFS(Graph g, int source, int N) {
        // create a queue used to do BFS
        Queue<Node> q = new ArrayDeque<>();
        HashMap<Integer, Integer> backtrack = new HashMap<>();

        // stores vertex is discovered or not
        // here [N+1] because the board starts from 1 and end at 100
        boolean[] discovered = new boolean[N+1];

        // mark source vertex as discovered
        discovered[source] = true;

        // assign minimum distance of source vertex as 0 and
        // push it into the queue
        Node node = new Node( source, 0 );
        q.add(node);

        //to backtrack
        backtrack.put(source, 0);

        // run till queue is not empty
        while (!q.isEmpty())
        {
            // pop front node from queue
            node = q.poll();

            // Stop BFS if we have reached last node
            if (node.ver == N)
            {
                System.out.println(node.minDist);

                int n = node.ver;

                while (n!=source){
                    System.out.print(n+" ");
                    n = backtrack.get(n);
                }
                System.out.println(" ");

                break;
            }

            // do for every adjacent node of current node
            for (int u : g.adjList.get(node.ver))
            {
                if (!discovered[u])
                {
                    // mark it discovered & push it into queue
                    discovered[u] = true;

                    // assign minimum distance of current node
                    // as minimum distance of parent node + 1
                    Node n = new Node(u, node.minDist + 1);
                    q.add(n);

                    backtrack.put(n.ver, node.ver);
                }
            }
        }
    }

    public static void findSolution(Map<Integer, Integer> ladder, Map<Integer, Integer> snake) {
        // Number of vertices in the graph
        int N = 10*10;
        int count = 0;
        
        // find all edges involved and store them in a vector
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < N; i++)
        {
            for (int j = 1; j <= 6 && i + j <= N; j++)
            {
                int src = i;

                // update destination if there is any ladder
                // or snake from current position.
                int dest;

                int _ladder = (ladder.get(i + j) != null) ? ladder.get(i + j): 0;
                int _snake = (snake.get(i + j) != null) ? snake.get(i + j): 0;

                if (_ladder != 0 || _snake != 0)
                    dest = _ladder + _snake;
                else
                    dest = i + j;

                // add edge from src to dest
                edges.add(new Edge(src, dest));
                count++;
            }
        }

        // construct directed graph
        Graph g = new Graph(edges, N);

        // Find Shortest path between 1 and 100 using BFS
        BFS(g, 1, N);

        //System.out.println("Number of Edges: "+count);
    }

    public static void main(String[] args) {
        // snakes and ladders are represented using a map.
        Map<Integer, Integer> ladder = new HashMap();
        Map<Integer, Integer> snake = new HashMap();

        // insert ladders into the map
        ladder.put(4, 25);
        ladder.put(13, 46);
        ladder.put(33, 49);
        ladder.put(42, 63);
        ladder.put(50, 69);
        ladder.put(62, 81);
        ladder.put(74, 92);

        // insert snakes into the map
        snake.put(27, 5);
        snake.put(40, 3);
        snake.put(43, 18);
        snake.put(54, 31);
        snake.put(66, 45);
        snake.put(76, 58);
        snake.put(89, 53);
        snake.put(99, 41);
/*
        // insert ladders into the map
        ladder.put(4, 14);
        ladder.put(9, 31);
        ladder.put(20, 38);
        ladder.put(28, 84);
        ladder.put(40, 59);
        ladder.put(51, 67);
        ladder.put(63, 81);
        ladder.put(71, 91);

        // insert snakes into the map
        snake.put(17, 7);
        snake.put(54, 34);
        snake.put(62, 19);
        snake.put(64, 60);
        snake.put(87, 24);
        snake.put(93, 73);
        snake.put(95, 75);
        snake.put(99, 78);*/

/*
        ladder.put(1, 38);
        ladder.put(4, 14);
        ladder.put(9, 31);
        ladder.put(21, 42);
        ladder.put(28, 84);
        ladder.put(51, 67);
        ladder.put(72, 91);
        ladder.put(80, 99);

        snake.put(17, 7);
        snake.put(54, 34);
        snake.put(62, 19);
        snake.put(64, 60);
        snake.put(87, 36);
        snake.put(93, 73);
        snake.put(95, 75);
        snake.put(98, 79);*/

        findSolution(ladder, snake);
    }
}