#688
Knight Probability in Chessboard
specialist · 770 · lc medium +31 · verified · 56.9% accepted · 4,021 likes · top 52%
Description
A chess knight is placed on an n x n board (0-indexed) at cell (row, column). It makes exactly k moves, each chosen uniformly at random from its eight L-shaped jumps regardless of whether the destination is on the board. The knight stops after k moves or when it leaves the board.
Return the probability that the knight is still on the board once all moves are completed.
Example 1:
Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.
Example 2:
Input: n = 1, k = 0, row = 0, column = 0
Output: 1.00000
Code
1
2
3