Description

Submission

class Solution {
    int n;
    pair<int, int> num2coord(int num) {
        int row, col;
        int reversedRow = (num - 1) / n;
        row = n - 1 - reversedRow; 
        int tempCol = (num - 1) % n;
        if(reversedRow % 2 == 0) {
            col = tempCol;
        } else {
            col = n - 1 - tempCol;
        }
        
        return {row, col};
    }
    
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        n = board.size();
        vector<int> dp(n * n + 1, INT_MAX);
        
        int ret = INT_MAX;
        
        queue<int> q; // cur, moved
        
        q.push(1);
        dp[1] = 0;
        
        while(!q.empty()) {
            auto cur = q.front(); 
            q.pop();
            int step = dp[cur];
            
            for(int i = 1; i <= 6; ++i) {
                int next = cur + i;
                if(next > n * n) break;
                
                auto [row, col] = num2coord(next);
                if(board[row][col] != -1) {
                
                    if(dp[board[row][col]] > step+1) {
                        dp[board[row][col]] = step+1;
                        q.push(board[row][col]);
                    }
                } else {
                    if(dp[next] > step + 1) {
                        dp[next] = step + 1;
                        q.push(next);
                    }
                }
            }

        }
        if(dp[n*n] == INT_MAX) return -1;
        return dp[n*n];
    }
};