314. Snakes and Ladders

Treat each square as a graph node with edges to the next 1-6 squares (following any snake or ladder at the landing square). The fewest moves to the last square is the shortest path from square 1, which BFS finds level by level.

Idea

Each die roll moves you 1–6 squares forward, and a snake/ladder instantly relocates you. So squares are graph nodes, and from square s you have edges to the final destinations of squares s+1 … s+6. "Fewest moves" is the shortest path in an unweighted graph — exactly what BFS computes, expanding one move-distance at a time.

Algorithm

1. Convert a label to board coordinates using the Boustrophedon (snake-order) mapping.
2. BFS from square 1, distance 0. For each square, try the next 6 labels; the neighbor is the snake/ladder destination if present, else the label itself.
3. Mark neighbors seen when first enqueued; the first time we dequeue n², its distance is the answer. If the queue empties, return -1.

Boustrophedon mapping

Labels start at the bottom-left and snake back and forth up the board. For label s: r, c = divmod(s-1, n); if r is odd, flip c to n-1-c; the board row is n-1-r.

Complexity

• Time: O(n²) — each square enqueued at most once, 6 edges each.
• Space: O(n²) for the visited set and queue.

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        int target = n * n;
        Set<Integer> seen = new HashSet<>();
        seen.add(1);
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{1, 0});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int s = cur[0], moves = cur[1];
            if (s == target) {
                return moves;
            }
            for (int nxt = s + 1; nxt <= Math.min(s + 6, target); nxt++) {
                int[] rc = pos(nxt, n);
                int val = board[rc[0]][rc[1]];
                int dest = val != -1 ? val : nxt;
                if (!seen.contains(dest)) {
                    seen.add(dest);
                    q.offer(new int[]{dest, moves + 1});
                }
            }
        }
        return -1;
    }

    private int[] pos(int square, int n) {
        int r = (square - 1) / n, c = (square - 1) % n;
        if (r % 2 == 1) {
            c = n - 1 - c;
        }
        return new int[]{n - 1 - r, c};
    }
}