package javaFixer; import java.util.LinkedList; import java.util.Queue; /** * Program #7 Program To find minimum no of Dice roll required * to win in given Snack and Ladder board * * @author JavaFixer * */ public class SnakeAndLadder { public static void main(String[] args) { int n = 100; int[] board = new int[n]; for (int i = 0; i < n; i++) { board[i] = -1; } // Ladder board[3] = 20; board[4] = 2; board[19] = 55; board[25] = 86; board[38] = 48; board[47] = 91; // Snakes board[98] = 8; board[88] = 28; board[70] = 60; board[55] = 41; board[37] = 7; board[25] = 10; System.out.println("Min Dice Roll required to win: " +getMinStepToWin(board,n)); } static int getMinStepToWin(int[] board, int n){ int[] visited = new int[n]; for(int i:visited){ visited[i] = 0; } CustomNode c = new CustomNode(); c.node = 0; c.distance = 0; Queue<CustomNode> q = new LinkedList<CustomNode>(); q.add(c); visited[0] = 1; while(!q.isEmpty()){ c = q.remove(); int currNode = c.node; int currDist = c.distance; if(currNode==n-1) { break; } for(int i=(currNode+1); i<=(currNode+6) && i<n;++i) { if(visited[i]==0) { CustomNode temp1 = new CustomNode(); if(board[i]!=-1) { temp1.node = board[i]; temp1.distance = currDist+1; }else { temp1.node = i; temp1.distance = currDist+1; } visited[i]=1; q.add(temp1); } } } return c.distance; } static class CustomNode{ int node; int distance; } }
Min Dice Roll required to win: 8