🎨Now live: Try our Free AI Image Generation Feature

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
- Mapping Board Position: - Convert a linear position (1 to n*n) to board coordinates considering the alternating row directions.
- 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, whereV
is the number of cells (n*n
) andE
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
};