Snakes and Ladders | Matrix Flattening | Leetcode 909

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();
        int MAX = n * n;
        queue<int> q;
        q.push(1);
        vector<bool> visited(MAX + 1, false);
        visited[1] = true;
        
        int level = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                int curr = q.front();
                q.pop();
                
                if (curr == MAX)
                    return level;
                
                for (int next = curr + 1; next <= min(curr + 6, MAX); ++next) {
                    int dest = next;
                    // Calculate board position
                    int row = (next - 1) / n;
                    int col = (next - 1) % n;
                    if (row % 2 == 1) // Odd rows are right-to-left
                        col = n - 1 - col;
                    
                    row = n - 1 - row; // Convert to board coordinates
                    
                    if (board[row][col] != -1)
                        dest = board[row][col];
                    
                    if (!visited[dest]) {
                        visited[dest] = true;
                        q.push(dest);
                    }
                }
            }
            level++;
        }
        return -1;
    }
};
/*
//JAVA
import java.util.*;

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int MAX = n * n;
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        boolean[] visited = new boolean[MAX + 1];
        visited[1] = true;
        
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int curr = q.poll();
                
                if (curr == MAX)
                    return level;
                
                for (int next = curr + 1; next <= Math.min(curr + 6, MAX); next++) {
                    int dest = next;
                    // Calculate board position
                    int row = (next - 1) / n;
                    int col = (next - 1) % n;
                    if (row % 2 == 1) // Odd rows are right-to-left
                        col = n - 1 - col;
                    
                    row = n - 1 - row; // Convert to board coordinates
                    
                    if (board[row][col] != -1)
                        dest = board[row][col];
                    
                    if (!visited[dest]) {
                        visited[dest] = true;
                        q.offer(dest);
                    }
                }
            }
            level++;
        }
        return -1;
    }
}

#Python
from collections import deque

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        MAX = n * n
        q = deque([1])
        visited = [False] * (MAX + 1)
        visited[1] = True
        
        level = 0
        while q:
            size = len(q)
            for _ in range(size):
                curr = q.popleft()
                
                if curr == MAX:
                    return level
                
                for next_pos in range(curr + 1, min(curr + 6, MAX) + 1):
                    dest = next_pos
                    # Calculate board position
                    row = (next_pos - 1) // n
                    col = (next_pos - 1) % n
                    if row % 2 == 1:  # Odd rows are right-to-left
                        col = n - 1 - col
                    
                    row = n - 1 - row  # Convert to board coordinates
                    
                    if board[row][col] != -1:
                        dest = board[row][col]
                    
                    if not visited[dest]:
                        visited[dest] = True
                        q.append(dest)
            level += 1
        return -1
*/