Knight Probability in Chessboard LeetCode solution in C++

1
class Solution {
2
 public:
3
  // declare a dp
4

5
  double dp[30][30][105];
6

7
  // x and y co-ordinates of 8 directions
8

9
  vector<int> dx = {-2, -2, -1, 1, 2, 2, 1, -1};
10

11
  vector<int> dy = {-1, 1, 2, 2, 1, -1, -2, -2};
12

13
  double dfs(int i, int j, int n, int moves) {
14
    // base case if we have reached out of grid
15

16
    if (i < 0 || i >= n || j < 0 || j >= n) return 0;
17

18
    // if no moves are remaining
19

20
    if (moves <= 0) return 1;
21

22
    // if already calculated
23

24
    if (dp[i][j][moves] != 0) return dp[i][j][moves];
25

26
    // find total possible ways of staying on chess board
27

28
    double ans = 0;
29

30
    for (int k = 0; k < 8; k++) {
31
      int new_row = i + dx[k];
32

33
      int new_col = j + dy[k];
34

35
      ans += dfs(new_row, new_col, n, moves - 1);
36
    }
37

38
    // for each cell there are 8 possible moves, so probablity will be no. of
39
    // successfull moves / 8
40

41
    // store the result and return
42

43
    return dp[i][j][moves] = ans / 8.0;
44
  }
45

46
  double knightProbability(int n, int k, int row, int column) {
47
    // initialize the dp with 0
48

49
    memset(dp, 0, sizeof(dp));
50

51
    return dfs(row, column, n, k);
52
  }
53
};