All problems

Snakes and Ladders

Medium · graph traversal

You are given a square board game as a grid board with n rows and n columns. The squares are numbered from 1 to n * n in a zigzag: square 1 is the bottom-left corner, the bottom row is numbered left to right, the row above it right to left, the next left to right again, and so on up to the top row.

You start on square 1. In one move you choose any number from 1 to 6 and move forward that many squares. You may not make a move that would take you past square n * n.

Each square holds a value in board, read at the cell where the square sits. If the value is -1, nothing special happens. Otherwise it is the number of a square (a ladder if it is higher than the one you are on, a snake if it is lower) and you must immediately go there. A move follows at most one such jump: if the square you are sent to also holds a number, you stay put on it.

Squares 1 and n * n always hold -1.

Return the fewest moves needed to land on square n * n, or -1 if it cannot be reached.

Examples

Example 1

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

Output: 2

Square 2 holds a ladder to square 14. Move 1: roll 1 to land on square 2 and climb to 14. Move 2: roll 2 to reach square 16.

Example 2

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

Output: 2

With no ladders or snakes, roll 6 to reach square 7 and then 2 to reach square 9.

Example 3

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

Output: -1

Squares 2 to 7 all send you back to square 1, so no roll from square 1 ever gets past them.

Constraints