Compute Knight Survival Probability after K Random Moves

### Problem A knight starts at (row,column) on an n-by-n board with zero-based coordinates. At each move it chooses uniformly among all eight knight offsets, including those that leave the board. It stops on leaving the board or after exactly k moves. Return the probability it remains on the board when it stops. ```cpp class Solution { public: double knightProbability(int n, int k, int row, int column); }; ``` ### Examples **Example 1:** ```text n = 3, k = 1, row = 0, column = 0 Output: 0.25 Explanation: Two of the eight offsets remain inside. ``` **Example 2:** ```text n = 2, k = 1, row = 1, column = 1 Output: 0.0 Explanation: Every knight offset leaves this board. ``` ### Constraints - Board side n: 1..25. Move count k: 0..100. Starting row and column are each in 0..n-1. ### Clarifying Questions Keep off-board move probability lost and distinguish exactly k attempted moves from conditioning on legal moves. ```hint Read the boundary condition What should happen to probability mass assigned to a move off the board? ``` ### Contract considerations Keep off-board move probability lost and distinguish exactly k attempted moves from conditioning on legal moves.