
### Problem Statement

###### On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The rows and columns are 0-indexed, so the top-left cell is (0, 0), and the bottom-right cell is (n - 1, n - 1).

###### A chess knight has eight possible moves it can make, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.

![Knight Probability](https://assets.leetcode.com/uploads/2018/10/12/knight.png)

###### Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

###### The knight continues moving until it has made exactly k moves or has moved off the chessboard.

###### Return the probability that the knight remains on the board after it has stopped moving.

**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.

**Steps To Solve**

- Think of solution without code

  - At each step the knight has to choose from 8 choices.
  - Lets understand this via diagram.
    - State 1 : Let the knight be in [2,2].We already have the knight at position r, c i.e[2,2] so the chance it lands there in 0 steps is 100%.
      ||0|1|2|3|4|
      |-|-|-|-|-|-|
      |0|0|0|0|0|0|
      |1|0|0|0|0|0|
      |2|0|0|1|0|0|
      |3|0|0|0|0|0|
      |4|0|0|0|0|0|
    - State 2:Probability of the knight in state 2 will be 1/8 in the location shown below as it can move to any of these 8 locations from [2,2].
      ||0|1|2|3|4|
      |-|-|-|-|-|-|
      |0|0|1/8|0|1/8|0|
      |1|1/8|0|0|0|1/8|
      |2|0|0|0|0|0|
      |3|1/8|0|0|0|1/8|
      |4|0|1/8|0|1/8|0|
    - State 3 : Our next distribution will look something like this.Example probability in [2][0] is 1/64 as in previous state probability in [0][1] was 1/8 so we multiplied it with 1/8 and added it to existing probability at [2][0] which is 0 .So 0+1/64 = 1/64.Similarly take [2][2] for example, all the 8 block with probabilty 1/8 in state 2 , will contribute to probability of [2][2] in state 3 so 8\*1/64 = 8/64.
      ||0|1|2|3|4|
      |-|-|-|-|-|-|
      |0|0|0|2/64|0|0|
      |1|0|2/64|0|2/64|0|
      |2|1/64|0|8/64|0|1/64|
      |3|0|2/64|0|2/64|0|
      |4|0|0|2/64|0|0|
  - We do this for k states and finally add all the probabilities to get the total probability.

```js
/**
 * @param {number} n
 * @param {number} k
 * @param {number} row
 * @param {number} column
 * @return {number}
 */
var knightProbability = function (n, k, row, column) {
  let curr = new Array(n).fill(0).map((arr) => new Array(n).fill(0));
  let next = new Array(n).fill(0).map((arr) => new Array(n).fill(0));

  curr[row][column] = 1;

  for (let m = 1; m <= k; m++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (curr[i][j] !== 0) {
          let paths = nextPath(n, i, j);

          for (let path of paths) {
            let [x, y] = path;
            next[x][y] += curr[i][j] / 8;
          }
        }
      }
    }
    curr = next;
    next = new Array(n).fill(0).map((arr) => new Array(n).fill(0));
  }

  let sum = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      sum += curr[i][j];
    }
  }

  return sum;
};

function isValid(n, i, j) {
  if (i >= 0 && i < n && j >= 0 && j < n) {
    return true;
  }

  return false;
}

function nextPath(n, i, j) {
  const paths = [
    [-2, 1],
    [-1, 2],
    [1, 2],
    [2, 1],
    [2, -1],
    [1, -2],
    [-1, -2],
    [-2, -1],
  ];

  let res = [];
  for (let path of paths) {
    let [x, y] = path;
    if (isValid(n, i + x, j + y)) {
      res.push([i + x, j + y]);
    }
  }

  return res;
}
```

###### Time and Space Complexity

Time Complexity is **O(N\*N\*K)**.
Space complexity in this case is **O(N\*N)**.
