Snakes and Ladders
Medium · Graphs · Explanation and code example
Breadth First Search - III
How it works
This optimization modifies the board in place to track visited squares, eliminating the need for a separate visited set or distance array. By marking visited positions directly on the board with a special value (0), we reduce memory overhead while maintaining the same BFS traversal logic.
Steps
- Initialize a queue with square 1 and mark the starting position on the board as visited (set to
0). - Process the queue level by level, tracking the current move count.
- For each square in the current level:
- Try all dice rolls (1 to 6).
- Skip if the next square exceeds the board.
- Apply any snake or ladder at the landing position.
- If the board position is not marked as visited (not
0), check for destination and enqueue. - Mark the position as visited by setting it to
0.
- Increment
movesafter processing each level and return-1if unreachable.
Complexity
- Time complexity:
O(n ^ 2) - Space complexity:
O(n ^ 2)
Things to watch for
Incorrect Square-to-Coordinate Conversion
The board uses a boustrophedon (zigzag) pattern starting from the bottom-left, with alternating row directions. A common mistake is not flipping the column index for odd rows or forgetting that row 0 in the board array corresponds to the top of the visual board. Always verify your conversion function with examples from different rows.
Marking the Wrong Square as Visited
After taking a snake or ladder, you land on a different square than where you initially rolled to. The visited check should be based on the final destination after any snake/ladder, but the board position to check for snakes/ladders is the intermediate square. Confusing these leads to revisiting squares or missing valid paths.
Not Handling Squares Beyond the Board
When rolling dice from a square close to the end, some rolls may exceed n * n. These rolls are invalid and should be skipped, not treated as reaching the destination. Always check nextSquare > n * n before processing a dice roll.
Python code example
from typing import List
from collections import deque
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
def intToPos(square):
r = (square - 1) // n
c = (square - 1) % n
if r % 2 == 1:
c = n - 1 - c
r = n - 1 - r
return r, c
q = deque([1])
board[n - 1][0] = 0
moves = 0
while q:
for _ in range(len(q)):
square = q.popleft()
for i in range(1, 7):
nextSquare = square + i
if nextSquare > n * n:
break
r, c = intToPos(nextSquare)
if board[r][c] != -1:
nextSquare = board[r][c]
if board[r][c] != 0:
if nextSquare == n * n:
return moves + 1
q.append(nextSquare)
board[r][c] = 0
moves += 1
return -1
C++ code example
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
queue<int> q;
q.push(1);
board[n - 1][0] = 0;
int moves = 0;
while (!q.empty()) {
for (int it = q.size(); it > 0; it--) {
int square = q.front(); q.pop();
for (int i = 1; i <= 6; i++) {
int nextSquare = square + i;
if (nextSquare > n * n) {
break;
}
auto [r, c] = intToPos(nextSquare, n);
if (board[r][c] != -1) {
nextSquare = board[r][c];
}
if (board[r][c] != 0) {
if (nextSquare == n * n) {
return moves + 1;
}
board[r][c] = 0;
q.push(nextSquare);
}
}
}
moves++;
}
return -1;
}
private:
pair<int, int> intToPos(int square, int n) {
int r = (square - 1) / n;
int c = (square - 1) % n;
if (r % 2 == 1) {
c = n - 1 - c;
}
r = n - 1 - r;
return {r, c};
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.