Showing posts with label ladder. Show all posts
Showing posts with label ladder. Show all posts

Find minimum no of Dice roll require to win in given Snack and Ladder board



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