Knight Probability in Chessboard
Problem statement
An n x n chessboard has its rows and columns numbered from 0 to n - 1. A knight starts on the cell in row row and column column, and it tries to make exactly k moves.
A knight move goes two cells in one direction and then one cell at a right angle, so a knight has 8 possible moves. For each move, the knight picks one of these 8 moves at random, each with the same chance, even if the move takes it off the board. If the knight lands off the board, it stays off and makes no more moves.
Return the probability that the knight is still on the board after it stops moving. Answers within 10^-5 of the correct value are accepted.
Function
knightProbability(n: int, k: int, row: int, column: int) → doubleExamples
Example 1
n = 3k = 2row = 0column = 0return = 0.0625From the corner (0, 0), only 2 of the 8 moves stay on the board: to (1, 2) and to (2, 1). From each of those two cells, again only 2 of the 8 moves stay on the board. So the chance is 2/8 * 2/8 = 1/16 = 0.0625.
Example 2
n = 4k = 1row = 1column = 1return = 0.5From (1, 1) on a 4 x 4 board, 4 moves stay on the board: to (0, 3), (2, 3), (3, 0) and (3, 2). The other 4 leave it. So the chance is 4/8 = 0.5.
Example 3
n = 1k = 0row = 0column = 0return = 1.0The knight makes no moves, so it is surely still on the board. The answer is 1.
Constraints
1 <= n <= 250 <= k <= 1000 <= row, column <= n - 1