LeetCode 909: Snakes and Ladders (BFS on Flattened Board)
English
Model each square as a graph node. From node x, you can roll 1..6 and move to x+d, then apply snake/ladder jump once. Since each roll has equal cost, BFS gives the minimum number of moves to reach n*n. The key implementation detail is converting square numbers to board coordinates in boustrophedon order.
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
boolean[] vis = new boolean[n * n + 1];
Queue q = new LinkedList<>();
q.offer(1);
vis[1] = true;
int steps = 0;
while (!q.isEmpty()) {
for (int sz = q.size(); sz > 0; sz--) {
int cur = q.poll();
if (cur == n * n) return steps;
for (int d = 1; d <= 6 && cur + d <= n * n; d++) {
int nxt = cur + d;
int[] rc = toRowCol(nxt, n);
if (board[rc[0]][rc[1]] != -1) nxt = board[rc[0]][rc[1]];
if (!vis[nxt]) {
vis[nxt] = true;
q.offer(nxt);
}
}
}
steps++;
}
return -1;
}
private int[] toRowCol(int num, int n) {
int r = (num - 1) / n;
int c = (num - 1) % n;
int row = n - 1 - r;
int col = (r % 2 == 0) ? c : (n - 1 - c);
return new int[]{row, col};
}
} class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
def to_row_col(num: int) -> tuple[int, int]:
r = (num - 1) // n
c = (num - 1) % n
row = n - 1 - r
col = c if r % 2 == 0 else n - 1 - c
return row, col
vis = [False] * (n * n + 1)
q = deque([1])
vis[1] = True
steps = 0
while q:
for _ in range(len(q)):
cur = q.popleft()
if cur == n * n:
return steps
for d in range(1, 7):
nxt = cur + d
if nxt > n * n:
break
r, c = to_row_col(nxt)
if board[r][c] != -1:
nxt = board[r][c]
if not vis[nxt]:
vis[nxt] = True
q.append(nxt)
steps += 1
return -1中文
把每个格子看成图上的一个节点。从 x 出发可掷 1..6 到 x+d，然后如果该格有蛇或梯子就立刻跳转一次。因为每次掷骰子的代价相同，使用 BFS 就能保证首次到达终点 n*n 时步数最小。实现难点主要是编号到二维坐标的牛耕式（蛇形）映射。
class Solution {
public int snakesAndLadders(int[][] board) {
int n = board.length;
boolean[] vis = new boolean[n * n + 1];
Queue q = new LinkedList<>();
q.offer(1);
vis[1] = true;
int steps = 0;
while (!q.isEmpty()) {
for (int sz = q.size(); sz > 0; sz--) {
int cur = q.poll();
if (cur == n * n) return steps;
for (int d = 1; d <= 6 && cur + d <= n * n; d++) {
int nxt = cur + d;
int[] rc = toRowCol(nxt, n);
if (board[rc[0]][rc[1]] != -1) nxt = board[rc[0]][rc[1]];
if (!vis[nxt]) {
vis[nxt] = true;
q.offer(nxt);
}
}
}
steps++;
}
return -1;
}
private int[] toRowCol(int num, int n) {
int r = (num - 1) / n;
int c = (num - 1) % n;
int row = n - 1 - r;
int col = (r % 2 == 0) ? c : (n - 1 - c);
return new int[]{row, col};
}
} class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
def to_row_col(num: int) -> tuple[int, int]:
r = (num - 1) // n
c = (num - 1) % n
row = n - 1 - r
col = c if r % 2 == 0 else n - 1 - c
return row, col
vis = [False] * (n * n + 1)
q = deque([1])
vis[1] = True
steps = 0
while q:
for _ in range(len(q)):
cur = q.popleft()
if cur == n * n:
return steps
for d in range(1, 7):
nxt = cur + d
if nxt > n * n:
break
r, c = to_row_col(nxt)
if board[r][c] != -1:
nxt = board[r][c]
if not vis[nxt]:
vis[nxt] = True
q.append(nxt)
steps += 1
return -1