n × n square given by the matrix board. Its cells are labeled 1 to n² in a zigzag: labeling starts at the bottom-left cell board[n-1][0] and runs right along the bottom row, the next row up runs right to left, the one above it left to right again, and so on.
A token starts on cell 1. Each turn you roll an ordinary six-sided die: from cell cur the token moves to any cell labeled from cur + 1 to min(cur + 6, n²), and you get to choose the roll.
If the destination cell has board[r][c] other than -1, it holds a shortcut (a lift up or a slide down), and the token must immediately move to the cell labeled board[r][c]. At most one shortcut is used per turn: if a shortcut lands on another shortcut, the second one is not taken. Cells 1 and n² have no shortcuts.
Return the fewest rolls needed to reach cell n², or -1 if it cannot be reached.board=[[-1, -1, -1], [-1, -1, -1], [-1, 9, -1]] → 1
The labels go 1, 2, 3 left to right on the bottom row, 4, 5, 6 right to left in the middle and 7, 8, 9 left to right on top. Rolling a 1 lands on cell 2, whose lift goes straight to 9. One roll is enough.
board=[[-1, -1, -1, -1], [-1, -1, -1, -1], [-1, -1, -1, -1], [-1, -1, -1, -1]] → 3
There are no shortcuts. Getting from 1 to 16 means covering 15 cells at most 6 per roll, so 3 rolls are needed (for example 1 → 7 → 13 → 16).
board=[[1, -1, -1], [1, 1, 1], [-1, 1, 1]] → -1
From cell 1 the token can only reach cells 2 to 7, and all of them send it back to 1. The finish is unreachable, so the answer is -1.
board is an n × n matrixboard[i][j] is -1 or between 1 and n²board=[[-1, -1, -1], [-1, -1, -1], [-1, 9, -1]]
1
Run checks the first 3 tests in your browser. Submit checks all 55 tests on the server, hidden ones included.