Chess Club Forward Knight Atlas
Path counts from top-left to each open grid cell via (1,2) or (2,1) moves
A chess club uses a rectangular practice board for a forward-only knight drill. The matrix blocked contains 0 for an available square and 1 for a closed square.
The knight starts at the top-left square, whose coordinates are (0, 0). From square (r, c), it may move only to:
(r + 1, c + 2), or(r + 2, c + 1).
A move is legal only if its destination is inside the board and available. As with an ordinary knight, the knight jumps: squares between the starting and destination squares do not affect the move.
Return an integer matrix with the same dimensions as blocked. Its entry at (r, c) must be the number of distinct legal move sequences that start at (0, 0) and end at (r, c), modulo 1,000,000,007.
The empty move sequence counts as one route to the starting square if that square is available. Closed squares have zero routes. If the starting square is closed, every entry of the returned matrix is zero.
Examples
Example 1
Input: blocked = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]] Output: [[1,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,2]]
On this open board, each of the two legal first moves is available. The bottom-right square can then be reached by taking the two move types in either order.
Example 2
Input: blocked = [[0,0,0,0],[0,0,1,0],[0,0,0,0],[0,0,0,0]] Output: [[1,0,0,0],[0,0,0,0],[0,1,0,0],[0,0,0,1]]
The closed square prevents the first move that lands at row 1, column 2. The route that first lands at row 2, column 1 remains legal. Closed squares that are merely jumped over do not matter.
Example 3
Input: blocked = [[0]] Output: [[1]]
The only square is available, so the empty move sequence is a route to it.
Constraints
- 1 <= len(blocked) <= 150
- 1 <= len(blocked[0]) <= 150
- All rows of blocked have the same length.
- Every entry of blocked is either 0 or 1.
Coordinates are zero-based. The returned matrix includes counts for every square, not just the bottom-right square. The intended solution takes O(rows * columns) time and uses O(rows * columns) space for the returned matrix.
Hints
Show hint 1Hint 1
Which two squares could be immediately before a particular destination in a legal route?
Show hint 2Hint 2
Process rows from top to bottom so that both predecessor counts are already known.
Follow-up questions
What an interviewer might ask once you have a working solution.
- If only the bottom-right route count is needed, how could you reduce the auxiliary memory?
- How would the recurrence change if a third allowed move were (r + 1, c + 1)?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem