algoadvance

Leetcode 909. Snakes and Ladders

Problem Statement

You are given a n x n integer matrix board where the cells are numbered from 1 to n^2 in a Boustrophedon style starting from the bottom-left of the board (i.e., if n is 5, the bottom left cell will be 1, the next cell is 2, and so on).

You start on square 1 of the board. In each move, starting from square k, you can move any number of cells from k+1 to k+6 (i.e., you can roll a 1, 2, 3, 4, 5, or 6-sided die).

If you land on a square with a ladder, you move to the destination of the ladder. Likewise, if you land on a square with a snake, you move to the destination of the snake.

The goal is to find the least number of moves required to reach the last square on the board. If it’s not possible to reach the last square, return -1.

Clarifying Questions

  1. Representation of Ladders and Snakes: Is it correct that if board[i][j] > 0, it indicates the destination square of either a snake or a ladder, and if board[i][j] == -1, it means no snake or ladder is present?

  2. Starting Point: Do we always start at cell 1, which corresponds to board[n-1][0]?

  3. Output: Should the output be the number of moves required to reach the last square, or -1 if it’s impossible?

Strategy

  1. Breadth-First Search (BFS): Since we need the minimum number of moves to reach the end, BFS is a suitable approach.

  2. Translation Function: We’ll need a function to convert the 1D board position into 2D matrix indices.

  3. Queue for BFS: We use a queue to manage cells to explore next and a set to track visited cells.

Code

Here is a possible implementation in C++:

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();
        
        // Transform 1D index to 2D coordinates
        auto getBoardValue = [&](int index) -> int {
            int r = (index - 1) / n, c = (index - 1) % n;
            if (r % 2 == 0) {
                c = n - 1 - c;
            }
            r = n - 1 - r;
            return board[r][c];
        };
        
        queue<int> q;
        q.push(1);
        unordered_set<int> visited;
        visited.insert(1);
        
        int moves = 0;
        
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                int curr = q.front();
                q.pop();
                
                if (curr == n * n) {
                    return moves;
                }
                
                for (int k = 1; k <= 6; ++k) {
                    int next = curr + k;
                    if (next > n * n) continue;
                    
                    int value = getBoardValue(next);
                    if (value == -1) {
                        value = next;
                    }
                    
                    if (!visited.count(value)) {
                        visited.insert(value);
                        q.push(value);
                    }
                }
            }
            ++moves;
        }
        
        return -1;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> board = {
        {-1,-1,-1,-1,-1},
        {-1,-1,-1,-1,-1},
        {-1,-1,-1,-1,-1},
        {-1,35,-1,-1,13},
        {-1,-1,-1,-1,-1}
    };
    
    cout << sol.snakesAndLadders(board) << endl;  // Output should be the least number of moves
    return 0;
}

Time Complexity

This solution efficiently finds the minimum number of moves required to reach the last square on the board, or determines if it is impossible.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI