909: Snakes-and-Ladders
Medium

code
- complexity
- time taken

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];
    }
};

909: Snakes-and-Ladders Medium

table of contents

code

complexity

time taken

909: Snakes-and-Ladders
Medium