You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:


	Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)].

	
		This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
	
	
	If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
	The game ends when you reach the square n2.


A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 do not have a snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent&nbsp;snake or ladder.


	For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.


Return the least number of moves required to reach the square n2. If it is not possible to reach the square, return -1.

&nbsp;
Example 1:

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.


Example 2:

Input: board = [[-1,-1],[-1,3]]
Output: 1


&nbsp;
Constraints:


	n == board.length == board[i].length
	2 &lt;= n &lt;= 20
	grid[i][j] is either -1 or in the range [1, n2].
	The squares labeled 1 and n2 do not have any ladders or snakes.


class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        
        # creating a borad map to loop-up the square value
        board_map = {}
        i = 1
        b_rev = board[::-1]
        for d, r in enumerate(b_rev):
			# reverse for even rows - here d is taken as direction 
            if d%2 != 0: r = r[::-1] 
            for s in r:
                board_map[i] = s
                i += 1
        
        # BFS Algorithm
        q = [(1, 0)] # (curr, moves)
        v = set()
        goal = len(board) * len(board) # end square
        
        while q:
            curr, moves = q.pop(0)
            # win situation
            if curr == goal: return moves
            # BFS on next 6 places (rolling a die)
            for i in range(1, 7):
                # skip square outside board
                if curr+i > goal: continue
                # get value from mapping
                next_pos = curr+i if board_map[curr+i] == -1 else board_map[curr+i]
                if next_pos not in v:
                    v.add(next_pos)
                    q.append((next_pos, moves+1))
        
        return -1
 
class Solution {
    //what if we have changed the dice number, or changing the starting index or changing the ending index
    //so i have covered all possible ways in which this question can be asked

//bfs tip:- for better bfs, we can use marking first and then inserting it in the queue which works faster then removing first and then checking
    public int [] getans(int dice,HashMap<Integer,Integer> map,int si,int ei){
        //if si==ei just directly return 
        if(si==ei) return new int [] {0,0,0};
        LinkedList<int[]> que = new LinkedList<>();
        que.addLast(new int[] {si,0,0});
        int level = 0;
        //to stop visiting cells again
        boolean [] vis = new boolean [ei+1];
        vis[si]=true;
        //starting bfs
        while(que.size()!=0){
            int size=que.size();
            while(size-->0){
                int [] rem = que.removeFirst();
                int idx= rem[0];
                int lad = rem[1];
                int sna = rem[2];
                for(int i=1;i<=dice;i++){
                    int x =i+rem[0]; //checking all the steps
                    if(x<=ei){ //valid points
                        if(map.containsKey(x)){ //this means that we have encountered a snake or a ladder
                            if(map.containsKey(x)){
                                int val = map.get(x); 
                                if(val==ei) return new int[] {level+1,lad+1,sna};
                                if(!vis[val]){
                                    vis[val]=true;
                                    //if val>x this means we have a ladder and if less, then it is a snake
                                    que.addLast(val>x? new int [] {val,lad+1,sna}:new int [] {val,lad,sna+1});
                                }
                            }
                        }
                        else{
                            //if it is not present in map, then it is a normal cell, so just insert it directly
                            if(x==ei) return new int [] {level+1,lad,sna};
                            if(!vis[x]){
                                vis[x]=true;
                                que.addLast(new int [] {x,lad,sna});
                            }
                        }
                    }
                }
            }
            level++;
        }
        return new int [] {-1,0,0};
    }
    public int snakesAndLadders(int[][] board) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int count = 1;
        int n = board.length;
        boolean flag = true;
        //traversing the board in the board game fashion and checking if the count that is representing the cell number, if we encounter something other then -1, then it can be a snake or it can be a ladder and mapping that cell index (i.e count to that number)
        for(int i=n-1;i>=0;i--){
            //traversing in the order of the board
            if(flag){
                for(int j=0;j<n;j++){
                    if(board[i][j]!=-1){
                        map.put(count,board[i][j]);   
                    }
                    count++;
                    flag=false;
                }
            }
            else{
                //reversing the direction
                for(int j=n-1;j>=0;j--){
                    if(board[i][j]!=-1){
                        map.put(count,board[i][j]);
                    }
                    flag=true;
                    count++;
                }
            }
        }
        //if snake on destination then just return -1;
        if(board[0][0]!=-1) return -1;
        //we only want the minimum steps, but for more conceptual approach for this question, {minm steps,ladders used, snakes used} 
        int [] ans = getans(6,map,1,n*n);;
        return ans[0];
        
    }
}
class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        unordered_map<int, int> mp;
        int n = board.size();
        for(int i = n-1; i >= 0; i--) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] != -1) {
                    int val;
                    if((n-i)%2 != 0) val = (n-i-1)*n + j + 1;
                    else val = (n-i-1)*n + n - j;
                    mp[val] = board[i][j];
                }
            }
        }
        queue<pair<int, int>> q;
        vector<int> visited(n*n+1, false);
        q.push({1, 0});
        while(!q.empty()) {
            int node = q.front().first;
            int moves = q.front().second;
            q.pop();
            if(node == n*n) return moves;
            if(visited[node]) continue;
            visited[node] = true;
            for(int k = 1; k <= 6; k++) {
                if(node+k > n*n) continue;
                int x = node + k;
                if(mp.find(x) != mp.end()) x = mp[x];
                q.push({x, moves+1});
            }
        }
        return -1;
    }
};
var snakesAndLadders = function(board) {
    let n = board.length;
  let seen = new Set();
  let queue = [[1, 0]];

  while (queue.length) {
    let [label, step] = queue.shift();
    //console.log(label, step);
    let [r, c] = labelToPosition(label, n);
    //console.log(r, c, n);
    if (board[r][c] !== -1) {
      label = board[r][c];
    }
    if (label == n * n) {
      return step;
    }
    for (let x = 1; x < 7; x++) {
      let nextLabel = label + x;
      if (nextLabel <= n * n && !seen.has(nextLabel)) {
        seen.add(nextLabel);
        queue.push([nextLabel, step + 1]);
      }
    }
  }
  return -1;
};

const labelToPosition = (label, n) => {
  let row = Math.floor((label - 1) / n);
  let col = (label - 1) % n;
  //console.log("label", row, col);
  if (row % 2 === 0) {
    return [n - 1 - row, col];
  } else {
    return [n - 1 - row, n - 1 - col];
  }
};
Snakes and Ladders