The Snakes and Ladders problem asks you to determine the minimum number of moves required to reach the last square on a n x n board, starting from the first square, following these rules:
-1 (an empty square), or a positive integer indicating the destination of a snake or ladder.1 (top-left, bottom row) and want to reach square n * n (bottom-right, top row).1 to 6 squares, unless you land on a square with a snake or ladder, in which case you must move to the destination square indicated in that cell.-1.The board is numbered in a Boustrophedon (zigzag) pattern: left to right on one row, then right to left on the next, and so on, starting from the bottom row.
At first glance, the problem resembles finding the shortest path in a board game, which suggests a graph traversal approach. Each square is a node, and each dice roll represents an edge to another node. However, the challenge lies in the board's zigzag numbering and the presence of snakes and ladders, which can "teleport" you to other squares.
A brute-force approach would try all possible dice rolls from every position, but this quickly becomes infeasible due to the exponential number of possibilities. Instead, we can use Breadth-First Search (BFS) to explore all possible moves level by level, ensuring we find the shortest path first.
The key is to carefully map between the 1D square number and the 2D board coordinates, accounting for the zigzag pattern. We also need to avoid revisiting squares to prevent infinite loops.
-1.We use a queue for BFS because it guarantees the shortest path is found first, and a visited set or array to prevent revisiting squares.
Suppose we have the following 3x3 board:
[
[-1, -1, 9],
[-1, -1, -1],
[2, -1, -1]
]
Numbering is as follows (bottom-left is 1, top-right is 9):
Let's trace the process:
The BFS ensures that the first time you reach square 9 is with the minimum number of moves.
The BFS approach is efficient and suitable for the problem's constraints.
The Snakes and Ladders problem is a shortest-path challenge on a special board. By modeling the board as a graph and using BFS, we efficiently find the minimum number of moves to reach the end, while handling the zigzag numbering and snake/ladder jumps. The key insights are mapping between 1D and 2D coordinates and leveraging BFS's level-order traversal to guarantee the shortest path.
from collections import deque
class Solution:
def snakesAndLadders(self, board):
n = len(board)
def get_rc(s):
quot, rem = divmod(s - 1, n)
row = n - 1 - quot
col = rem if quot % 2 == 0 else n - 1 - rem
return row, col
visited = set()
queue = deque()
queue.append((1, 0)) # (square, moves)
visited.add(1)
while queue:
s, moves = queue.popleft()
if s == n * n:
return moves
for i in range(1, 7):
next_s = s + i
if next_s > n * n:
continue
r, c = get_rc(next_s)
if board[r][c] != -1:
next_s = board[r][c]
if next_s not in visited:
visited.add(next_s)
queue.append((next_s, moves + 1))
return -1
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
auto get_rc = [n](int s) {
int quot = (s - 1) / n, rem = (s - 1) % n;
int row = n - 1 - quot;
int col = (quot % 2 == 0) ? rem : n - 1 - rem;
return make_pair(row, col);
};
vector<bool> visited(n * n + 1, false);
queue<pair<int, int>> q;
q.push({1, 0});
visited[1] = true;
while (!q.empty()) {
auto [s, moves] = q.front(); q.pop();
if (s == n * n) return moves;
for (int i = 1; i <= 6; ++i) {
int next_s = s + i;
if (next_s > n * n) continue;
auto [r, c] = get_rc(next_s);
if (board[r][c] != -1) next_s = board[r][c];
if (!visited[next_s]) {
visited[next_s] = true;
q.push({next_s, moves + 1});
}
}
}
return -1;
}
};
import java.util.*;
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
boolean[] visited = new boolean[n * n + 1];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{1, 0});
visited[1] = true;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int s = curr[0], moves = curr[1];
if (s == n * n) return moves;
for (int i = 1; i <= 6; ++i) {
int next_s = s + i;
if (next_s > n * n) continue;
int[] rc = getRC(next_s, n);
int r = rc[0], c = rc[1];
if (board[r][c] != -1) next_s = board[r][c];
if (!visited[next_s]) {
visited[next_s] = true;
queue.offer(new int[]{next_s, moves + 1});
}
}
}
return -1;
}
private int[] getRC(int s, int n) {
int quot = (s - 1) / n, rem = (s - 1) % n;
int row = n - 1 - quot;
int col = (quot % 2 == 0) ? rem : n - 1 - rem;
return new int[]{row, col};
}
}
/**
* @param {number[][]} board
* @return {number}
*/
var snakesAndLadders = function(board) {
const n = board.length;
function getRC(s) {
const quot = Math.floor((s - 1) / n);
const rem = (s - 1) % n;
const row = n - 1 - quot;
const col = (quot % 2 === 0) ? rem : n - 1 - rem;
return [row, col];
}
const visited = new Array(n * n + 1).fill(false);
const queue = [];
queue.push([1, 0]);
visited[1] = true;
while (queue.length > 0) {
const [s, moves] = queue.shift();
if (s === n * n) return moves;
for (let i = 1; i <= 6; ++i) {
let next_s = s + i;
if (next_s > n * n) continue;
const [r, c] = getRC(next_s);
if (board[r][c] !== -1) next_s = board[r][c];
if (!visited[next_s]) {
visited[next_s] = true;
queue.push([next_s, moves + 1]);
}
}
}
return -1;
};