Problem #909: Snakes and Ladders

Intuition & Strategy Breakdown

Flatten 2D Snakes & Ladders board into 1D array mapping 1..N^2. Run BFS finding minimum dice rolls to reach square N^2.

Python Solution

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        def get_pos(label):
            r, c = divmod(label - 1, n)
            actual_r = n - 1 - r
            actual_c = c if r % 2 == 0 else n - 1 - c
            return actual_r, actual_c
        
        queue = collections.deque([(1, 0)])
        visited = {1}
        
        while queue:
            curr, moves = queue.popleft()
            for i in range(1, 7):
                nxt = curr + i
                if nxt > n * n: break
                r, c = get_pos(nxt)
                dest = board[r][c] if board[r][c] != -1 else nxt
                if dest == n * n: return moves + 1
                if dest not in visited:
                    visited.add(dest)
                    queue.append((dest, moves + 1))
        return -1

Java Solution

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int[] flatBoard = new int[n * n + 1];
        boolean leftToRight = true;
        int index = 1;
        for (int r = n - 1; r >= 0; r--) {
            if (leftToRight) {
                for (int c = 0; c < n; c++) flatBoard[index++] = board[r][c];
            } else {
                for (int c = n - 1; c >= 0; c--) flatBoard[index++] = board[r][c];
            }
            leftToRight = !leftToRight;
        }
        
        Queue q = new LinkedList<>();
        q.offer(1);
        int[] dist = new int[n * n + 1];
        Arrays.fill(dist, -1);
        dist[1] = 0;
        
        while (!q.isEmpty()) {
            int curr = q.poll();
            for (int i = 1; i <= 6; i++) {
                int nxt = curr + i;
                if (nxt > n * n) break;
                int dest = flatBoard[nxt] == -1 ? nxt : flatBoard[nxt];
                if (dest == n * n) return dist[curr] + 1;
                if (dist[dest] == -1) {
                    dist[dest] = dist[curr] + 1;
                    q.offer(dest);
                }
            }
        }
        return -1;
    }
}