550/670

550. Snakes and Ladders

Medium

You are handed an n x n Snakes and Ladders board as the matrix board, where row 0 is the top row. The playing squares are numbered 1 to n² starting at the bottom-left corner: the bottom row runs left to right, the row above it right to left, and so on, alternating direction all the way up (a boustrophedon path).

You begin on square 1. On each move you choose any die value from 1 to 6 and advance that many squares — you may never move past n². If the square you land on holds a value v other than -1, a snake or ladder instantly carries you to square v. Taking it is mandatory, but it happens at most once per move: if v is itself the start of another snake or ladder, you stay on v and do not ride again.

Return the minimum number of moves needed to stand on square n², or -1 if it is impossible. Squares 1 and n² never hold a snake or ladder.

Example 1: the numbered board and the ladder from 2 to 9The faint dotted line shows the boustrophedon numbering path from square 1 to square 9. Landing on square 2 triggers its ladder (gold) immediately, ending the move on square 9.

Example 1:

Input: board = [[-1,-1,-1],[-1,-1,-1],[-1,9,-1]]

Output: 1

Explanation: Square 2 (bottom row, second square) holds a ladder to square 9. Roll a 1: you land on square 2 and the ladder carries you straight to square 9 = n². One move.

Example 2:

Input: board = [[1,1,-1],[1,1,1],[-1,1,1]]

Output: -1

Explanation: From square 1 a die reaches squares 2 through 7 — but every one of them is a snake that slides you back to square 1. Squares 8 and 9 can never be reached, so the answer is -1.

Constraints:

n == board.length == board[i].length
2 ≤ n ≤ 20
board[i][j] is -1 or an integer in [1, n²]
The squares numbered 1 and n² hold -1 (no snake or ladder).

Hints:

Forget the grid for a moment: every square is a node, and one move connects a square to (up to) six later squares. "Fewest moves" on unit-cost edges is a shortest-path question — breadth-first search answers it.

Write one helper that converts a square label to its board value: row_from_bottom = (label − 1) / n, offset = (label − 1) mod n, and flip the offset on odd rows from the bottom. Getting this conversion right is half the problem.

Apply the portal to the square you LAND on, exactly once, and mark visited by the square you END the move on. Visiting by landing square instead lets snakes create infinite loops.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: board = [[-1,-1,-1],[-1,-1,-1],[-1,9,-1]]

Expected output: 1