Snakes and Ladders — Editorial

Opening the reading…

Intuitionwhy the game is an unweighted shortest-path problem

Treat every square label from 1 to n² as a node. From a current square, one dice roll can reach up to six next labels, and a snake or ladder changes that chosen label into the square where you actually land. Therefore, each dice roll is one graph edge, even when the edge includes a snake or ladder.

Every edge has the same cost: one roll. BFS is designed to find the smallest number of equal-cost edges from a starting node to a target node. It explores all positions reachable in zero rolls, then all positions reachable in one roll, then two rolls, and so on. The first time it removes the final square from the queue, its distance is minimal.

The only board-specific detail is converting a one-dimensional label into a matrix cell. Labels rise from the bottom row, reverse direction on the next row, and continue alternating. Once that coordinate is correct, a move is simple: choose a label at most six ahead, inspect its cell, and take one jump if the cell contains one.

DIAGRAM — NOT DRAWN YET

The figure shows a square board whose bottom row is labeled from left to right starting at 1, while the row above is labeled from right to left, demonstrating the alternating Boustrophedon order. A marked current square has up to six arrows to the next labels. One arrow ends on a cell containing a snake or ladder and continues once to its destination. The marked squares are arranged into BFS layers by dice-roll count, making equal-cost shortest paths visible.

The board is the graph: labels are nodes, dice rolls are edges, and jumps alter one edge's endpoint.

Approachsix steps from labels to the shortest roll count

Write a coordinate function that converts a square label into its matrix row and column, because the board is stored in alternating directions rather than in ordinary top-to-bottom order.

Create a distance array indexed by square label and set every entry to -1, then set distance[1] to 0, because the first visit to a square in BFS is its shortest known route and -1 can mark an unvisited square.

Put square 1 into a queue, because BFS must process positions in the order of their distance from the start rather than in an arbitrary order.

Remove the front square and try step values from 1 through 6, stopping at n², because one roll has at most six outcomes and cannot move beyond the final square.

Convert each chosen label to coordinates, apply board[row][column] when it is not -1, and do not inspect the resulting square again, because the rules allow exactly one snake or ladder per roll.

If the landed square is unvisited, assign it distance[cur] + 1 and enqueue it; otherwise skip it, because revisiting a square cannot improve the distance that BFS already assigned.

Return the target distance when the target is reached, and return -1 if the queue empties first, because an empty BFS means no sequence of legal rolls can reach the final square.

Complexitythe board has n² possible graph nodes

MEASURE	BOUND	WHY
Time	O(n²)	There are n² labels, and each label is removed from the queue at most once. Each removal examines at most six die outcomes and performs constant-time coordinate and jump work, so the total is at most 6n², which simplifies to O(n²).
Space	O(n²)	The distance array and queue can together hold information for every square in the worst case, such as when many positions become reachable before the target is processed. The board itself is input storage, and there is no returned collection whose storage needs to be counted; the extra working space is O(n²).

Here n is the board side length, so the number of square labels is n².

Annotated solutionC++ · BFS over square labels with a Boustrophedon coordinate map

CPPBFS visits each square once and applies the selected square's snake or ladder exactly once.

#include <vector>
#include <queue>
#include <utility>

using namespace std;

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();
        int target = n * n;

        auto coord = [&](int square) -> pair<int, int> {
            int zeroBased = square - 1;
            int rowFromBottom = zeroBased / n;
            int offset = zeroBased % n;

            int row = n - 1 - rowFromBottom;
            int col = (rowFromBottom % 2 == 0)
                          ? offset
                          : n - 1 - offset;
            return {row, col};
        };

        vector<int> distance(target + 1, -1);
        queue<int> pending;
        distance[1] = 0;
        pending.push(1);

        while (!pending.empty()) {
            int current = pending.front();
            pending.pop();

            if (current == target) {
                return distance[current];
            }

            for (int step = 1; step <= 6 && current + step <= target; ++step) {
                int next = current + step;
                auto [row, col] = coord(next);

                if (board[row][col] != -1) {
                    next = board[row][col];
                }

                if (distance[next] == -1) {
                    distance[next] = distance[current] + 1;
                    pending.push(next);
                }
            }
        }

        return -1;
    }
};

The coordinate function first measures the label's zero-based row from the bottom. That row determines the matrix row and also the direction: even rows from the bottom run left to right, while odd rows run right to left. Keeping this conversion in one function prevents the BFS logic from mixing graph traversal with board geometry.