272. Knight Stays On
A chess knight is placed on square (row, col) of an n x n board (rows and columns numbered from 0). It then makes up to k moves. For every move it picks uniformly at random one of its 8 standard knight moves, (+-1,+-2) and (+-2,+-1), whether or not the destination is on the board. Once it steps off the board it is gone and makes no further moves.
Return, as a double, the probability that the knight is still on the board after the k moves. With k = 0 that probability is 1. Answers within 1e-9 are accepted. Use dynamic programming over (move number, square): O(k * n^2) time and O(n^2) space.
Example 1
- Input:
- n = 6k = 3row = 2col = 3
- Output:
- 0.359375
- Explanation:
On a 6x6 board a knight at (2,3) has 8 legal moves available at first, but several of the 512 three-move paths fall off, leaving a survival probability of 0.359375.
Example 2
- Input:
- n = 3k = 2row = 0col = 0
- Output:
- 0.0625
- Explanation:
From the corner of a 3x3 board 2 of 8 moves stay on, and each landing square again has 2 safe moves, giving (2/8)*(2/8)=1/16.
Example 3
- Input:
- n = 9k = 0row = 4col = 4
- Output:
- 1
- Explanation:
With zero moves the knight has not moved, so it is certainly still on the board.
Constraints
1 ≤ n ≤ 25
0 ≤ k ≤ 100
0 ≤ row, col < n
Absolute error up to 1e-9 is accepted.
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-9: |answer - expected| <= 1.0E-9 x max(1, |expected|).
- Tolerance
1e-9
Expected complexity
- Time
- O(k * n^2)
- Space
- O(n^2)