459. Knight Probability in Chessboard
A chess knight stands on an n × n board at cell (row, column) (0-indexed, row 0 at the top). It will attempt exactly k moves. On every attempt it picks one of the knight's 8 L-shaped jumps uniformly at random — two cells along one axis and one along the other — without looking at where it will land. The moment it lands outside the board it falls off and makes no further moves.
Return the probability that the knight is still on the board after all k attempts. Print the probability rounded to exactly 5 digits after the decimal point (for example 0.06250).
Example 1:
Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: From the corner of a 3×3 board only 2 of the 8 jumps stay on the board — to (1,2) and (2,1) — so the first move survives with probability 2/8. From either of those squares, again exactly 2 of 8 jumps stay on. Total: (2/8) × (2/8) = 1/16 = 0.0625.
Example 2:
Input: n = 1, k = 0, row = 0, column = 0
Output: 1.00000
Explanation: Zero moves are attempted, so the knight never risks falling off: probability 1.
Constraints:
- 1 ≤ n ≤ 25
- 0 ≤ k ≤ 100
- 0 ≤ row, column ≤ n - 1
Hints:
Enumerating paths is hopeless (8^k of them), but a path only matters through where it currently is. The chance of surviving the rest depends solely on (current cell, moves remaining) — a textbook DP state.
Push probability mass forward: start a grid with 1.0 at the start cell, and for each of k rounds send each cell's mass out in 8 equal shares of 1/8, keeping only the shares that land on the board. The answer is the sum of the final grid; two n×n layers are all the memory you need.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3, k = 2, row = 0, column = 0
Expected output: 0.06250