909: Snakes-and-Ladders
Medium

Basically just a breadth-first search question. Note, for the remainder of the question, the squares on the board will be 0-indexed.

First, we keep a matrix minSteps which tracks the minimum number of dice rolls taken to reach a certain cell. It is initialized with all values set to -1.

Then, initialize a queue with square 0 inside and the bottom left of the board (the start of the board) set to a distance of 0.

Now, starting with distance = 1, for each iteration (in otherwords, at each value of distance), we:

Now, if the queue is empty or the last cell on the board has been traversed, we can exit the while loop and simply return the minimum number of dice rolls taken to reach the last cell on the board stored inside the matrix minPlace.

Code:

class Solution {
public:
    pair<int, int> findCoords(int boardLength, int square) {
        int row = square/boardLength;
        if (row%2 != 0) {
            return {boardLength-1 - row, boardLength-1 - square%boardLength};
        } else {
            return {boardLength-1 - row, square%boardLength};
        }
    }
    int snakesAndLadders(vector<vector<int>>& board) {
        int boardLength = (int) board.size();
        int maxBoardSize = (int) boardLength * boardLength;
        int maxSquareCol = (boardLength % 2 == 0) ? 0 : board.size()-1;
        vector<vector<int>> minSteps (boardLength, vector<int> (boardLength, -1));

        queue<int> q;
        q.push(0);

        minSteps[boardLength-1][0] = 0;
        int distance = 1;
        while (!q.empty() && minSteps[0][maxSquareCol] == -1) {
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                int square = q.front();
                q.pop();

                for (int j = 1; j <= 6 && square+j < maxBoardSize; ++j) {
                    int targetSquare = square+j;
                    pair<int, int> targetCoords = findCoords(boardLength, targetSquare);
                    if (minSteps[targetCoords.first][targetCoords.second] == -1 && board[targetCoords.first][targetCoords.second] == -1) {
                        minSteps[targetCoords.first][targetCoords.second] = distance;
                        q.push(targetSquare);
                    } else if (board[targetCoords.first][targetCoords.second] != -1) {
                        targetSquare = board[targetCoords.first][targetCoords.second]-1;
                        targetCoords = findCoords(boardLength, targetSquare);
                        if (minSteps[targetCoords.first][targetCoords.second] == -1) {
                            minSteps[targetCoords.first][targetCoords.second] = distance;
                            q.push(targetSquare);
                        }
                    }
                }
            }
            ++distance;
        }
        return minSteps[0][maxSquareCol];
    }
};

Complexity:

Time Taken: