Created
March 30, 2018 20:43
-
-
Save Zoha131/3cf496ef3234052982b8c76408ef4a14 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment