[JAVA] [BFS] Detailed Solution

interview-questions
programming
Tags: #<Tag:0x00007f242dbadeb8> #<Tag:0x00007f242dbadc38>

#1

So this is a typical question of BFS, where the ans lies in finding the min distance(steps) required to reach 100 from 1.

public int snakeLadder(int[][] lad, int[][] sna) {
    map = new HashMap<>();
    visited = new boolean[101];
    
    for(int[] row : lad){
        int u = row[0];
        int v = row[1];
        map.put(u, v);
    }
    
    for(int[] row : sna){
        int u = row[0];
        int v = row[1];
        map.put(u, v);
    }
    return minRolls();
}

private Map<Integer, Integer> map;
private boolean[] visited;

private int minRolls(){
    Queue<Integer> queue = new LinkedList<>();
    queue.add(1);
    
    int level = 1;
    
    while(!queue.isEmpty()){
        int size = queue.size();
        while(size-- > 0){
            int cn = queue.remove();
            
            visited[cn] = true;
            
            for(int i = 1; i <= 6; i++){
                int lp = cn + i;
                if(map.containsKey(lp)){
                    lp = map.get(lp);
                }
                
                if(lp == 100)
                    return level;
                
                if(!visited[lp]){
                    queue.add(lp);
                }
            }
        }
        level++;
    }
    
    return -1;
}