909. Snakes and Ladders

Description

The problem involves playing a game on an n x n board where the cells contain either -1 (indicating an empty cell) or a positive integer (indicating a snake or a ladder that transports the player to another cell). The goal is to determine the minimum number of moves required to reach the last cell from the first cell.

Intuition

The problem can be approached as a shortest path problem on an unweighted graph, where each cell in the board represents a node, and each move (from 1 to 6 cells forward) represents an edge. Breadth-First Search (BFS) is a suitable algorithm to find the shortest path in an unweighted graph.

Approach

1. Mapping Board Position: - Convert a linear position (1 to n*n) to board coordinates considering the alternating row directions.
2. Breadth-First Search (BFS): - Initialize a queue for BFS with the starting position (1, 0) indicating the first cell and 0 moves. - For each position, try moving 1 to 6 steps forward. - If a snake or ladder is found, move directly to the target cell. - If the last cell (n*n) is reached, return the number of moves. - Use a set to keep track of visited positions to avoid cycles.

Complexity

Time Complexity:

• BFS explores each cell at most once, resulting in O(V + E) time complexity, where V is the number of cells (n*n) and E is the number of possible moves (6 per cell). Hence, O(n^2).

Space Complexity:

• The space used by the queue and the visited set is O(n^2).

Code

C++

class Solution {
public:
    int snakesAndLadders(vector>& board) {
        int n = board.size();
        set visited;
        auto getPos = [&](int pos) {
            int row = (pos - 1) / n;
            int col = (pos - 1) % n;
            if (row % 2 == 1) col = n - 1 - col;
            row = n - 1 - row;
            return make_pair(row, col);
        };
        queue> q;
        q.push({1, 0});

        while (!q.empty()) {
            auto [pos, moves] = q.front();
            q.pop();

            for (int i = 1; i < 7; ++i) {
                int newPos = i + pos;
                auto [r, c] = getPos(newPos);

                if (board[r][c] != -1) newPos = board[r][c];
                if (newPos == n * n) return moves + 1;

                if (!visited.count(newPos)) {
                    visited.insert(newPos);
                    q.push({newPos, moves + 1});
                }
            }
        }
        return -1;
    }
};

Python

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        
        def getPos(pos: int) -> (int, int):
            row = (pos - 1) // n
            col = (pos - 1) % n
            if row % 2 == 1:
                col = n - 1 - col
            row = n - 1 - row
            return row, col

        visited = set()
        queue = deque([(1, 0)])  # (position, moves)
        while queue:
            pos, moves = queue.popleft()
            for i in range(1, 7):
                newPos = pos + i
                if newPos > n * n:
                    break
                r, c = getPos(newPos)
                if board[r][c] != -1:
                    newPos = board[r][c]
                if newPos == n * n:
                    return moves + 1
                if newPos not in visited:
                    visited.add(newPos)
                    queue.append((newPos, moves + 1))
        
        return -1

Java

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        Set visited = new HashSet<>();
        
        Queue queue = new LinkedList<>();
        queue.offer(new int[]{1, 0});  // Start from position 1 with 0 moves
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int pos = current[0];
            int moves = current[1];
            
            for (int i = 1; i <= 6; i++) {
                int newPos = pos + i;
                if (newPos > n * n) break;
                int[] coordinates = getPos(newPos, n);
                int r = coordinates[0];
                int c = coordinates[1];
                
                if (board[r][c] != -1) newPos = board[r][c];
                if (newPos == n * n) return moves + 1;
                
                if (!visited.contains(newPos)) {
                    visited.add(newPos);
                    queue.offer(new int[]{newPos, moves + 1});
                }
            }
        }
        return -1;
    }
    private int[] getPos(int pos, int n) {
        int row = (pos - 1) / n;
        int col = (pos - 1) % n;
        if (row % 2 == 1) col = n - 1 - col;
        row = n - 1 - row;
        return new int[]{row, col};
    }
}

JavaScript

var snakesAndLadders = function (board) {
    let n = board.length;
    let set = new Set();
    let getPos = (pos) => {
        let row = Math.floor((pos - 1) / n)
        let col = (pos - 1) % n
        col = row % 2 == 1 ? n - 1 - col : col;
        row = n - 1 - row;
        return [row, col]
    }
    let q = [[1, 0]]
    while (q.length > 0) {
        [pos, moves] = q.shift();
        for (let i = 1; i < 7; i++) {
            let newPos = i + pos;
            let [r, c] = getPos(newPos);
            if (board[r][c] != -1) newPos = board[r][c]
            if (newPos == n * n) return moves + 1;
            if (!set.has(newPos)) {
                set.add(newPos)
                q.push([newPos, moves + 1])
            }
        }
    }
    return -1
};