A knight stands on square (row, col) of an n x n board (0-indexed). It makes exactly k moves; each move is one of the 8 knight moves chosen uniformly at random, even if it leaves the board. Once it's off the board it stays off and stops moving.
Write knight_probability(n: int, k: int, row: int, col: int) -> float returning the probability that the knight is still on the board after all k moves. Answers within 1e-6 are accepted.
Constraints: 1 <= n <= 25, 0 <= k <= 100, 0 <= row, col < n.
knight_probability(3, 1, 0, 0) # 0.25: only 2 of the 8 moves stay on a 3x3 board
knight_probability(1, 0, 0, 0) # 1.0: no moves, still on the board
knight_probability(1, 1, 0, 0) # 0.0
Following every sequence of moves is 8^k paths; aim for O(k * n^2).
Show hint
Work move by move: if you know, for every square, the probability of standing there after m moves, you can compute the same table for m + 1 moves.