Snakes and Ladders

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:

find the size of the queue, n

there are n cells, that can be reached in the same number of dice rolls, that we want to pop from the queue

for each cell we pop, we check all the cells from cell + 1 to cell + 6 and check if they have been visited already

we can check this by checking if its cell in minPlace is not equal to -1

EXCEPTION: if there is a snake or ladder starting from that cell, we instead check if the destination of the snake or ladder in minPlace is not equal to -1

if the cell we checked has not been visited, we can set its minPlace to distance and push the cell into the queue

finally, increment distance

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: O(n^2) where n is the size of boards (side length of the board)

Space: O(n^2)

time taken

31 minutes and 54 seconds

lowkey, maybe the tech is to just stop misreading the question-