class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();

        // Create a mapping between pos and {row,col}
        vector<pair<int,int>> posMap(n * n + 1);
        int pdx = 1;
        int revFlag = 0; // col is reverse
        
        for(int row = n - 1; row >= 0; row--) {
            for(int col = 0; col < n; col++) {
                posMap[pdx++] = (revFlag == 0) ? make_pair(row, col) : make_pair(row, n - 1 - col);
            }
            revFlag = !revFlag; // reverse the flag
        }

        vector<int> dist(n * n + 1, -1);
        dist[1] = 0;    // start from 1
        queue<int> que;
        que.push(1);

        // start BFS
        while(!que.empty()) {
            int curr = que.front();
            que.pop();

            for(int next = curr + 1; next <= min(curr + 6, n * n); next++) {
                // fetch row and col from posMap
                auto [row, col] = posMap[next];
                // calculate the destination
                // if there is a stairs or snake, move to new pos
                // otherwise, just move to next
                int destination = board[row][col] != -1 ? board[row][col] : next;

                // if we do not visit destination before, move from curr and add one step
                if(dist[destination] == -1) {
                    dist[destination] = dist[curr] + 1;
                    que.push(destination);
                }
            }
        }
        return dist[n * n];
    }
};