668. Board Game Climb
A racing board game is laid out as an n x n grid and its squares are numbered 1 to n*n in a zig-zag: square 1 is the bottom-left cell, numbers rise left to right along the bottom row, then right to left along the row above, and so on, reversing direction on each row. The grid board tells what is printed on each cell: -1 means an ordinary square, and any other value v is a shortcut or a trap that moves a token straight to square v. Squares 1 and n*n are always ordinary.
A token starts on square 1. In one turn it rolls any number from 1 to 6 and moves forward that many squares; a roll that would pass the last square is not allowed. If the square it lands on has a value other than -1, it is moved to that square at once, but that second square is never followed again in the same turn. Return the fewest turns needed to land on square n*n, or -1 if it cannot be done.
Example 1
- Input:
- board = [[-1,-1,-1,-1],[-1,-1,-1,-1],[-1,-1,-1,-1],[-1,-1,14,-1]]
- Output:
- 2
- Explanation:
Square 3 (bottom row, third cell) holds 14. Roll 2 to land on square 3 and ride to square 14, then roll 2 to reach square 16: two turns.
Example 2
- Input:
- board = [[1,-1,-1],[1,1,1],[-1,1,1]]
- Output:
- -1
- Explanation:
Every square from 2 to 7 sends the token back to square 1, so the token can never get past them and the answer is -1.
Constraints
1 ≤ n ≤ 200
each cell is -1 or an integer in the range [1, n*n]
the cells for squares 1 and n*n hold -1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n^2)