Knight Reachability
MediumGraph · Google
A knight stands on a rows x cols board at cell start = [r, c] (0-indexed). In one move it jumps two cells in one direction and one cell in a perpendicular direction, for up to 8 possible moves; a move that would leave the board is not allowed.
Return True if the knight can reach cell target using at most max_moves moves, and False otherwise. If start equals target, zero moves are needed.
Note that some cells may be unreachable altogether on small or narrow boards.
Example 1
- Input:
- rows = 5, cols = 5, start = [0, 0], target = [4, 4], max_moves = 4
- Output:
- True
- Explanation
- The route (0, 0) -> (1, 2) -> (2, 4) -> (3, 2) -> (4, 4) takes 4 moves. No shorter route exists, because each move changes
row + colby at most 3 and two moves cannot cover the needed 8, so the limit of 4 is just enough.
Example 2
- Input:
- rows = 5, cols = 5, start = [0, 0], target = [1, 1], max_moves = 1
- Output:
- False
- Explanation
- A diagonal neighbor is never one knight move away. On a 5 x 5 board reaching (1, 1) from the corner takes 4 moves, which exceeds the limit of 1.
Example 3
- Input:
- rows = 3, cols = 3, start = [0, 0], target = [1, 1], max_moves = 100
- Output:
- False
- Explanation
- On a 3 x 3 board every knight move from any edge cell lands on another edge cell, so the center can never be reached no matter how many moves are allowed.
Constraints
1 <= rows, cols <= 500startandtargetare cells on the board0 <= max_moves <= 10^6