Skip to content

688. Knight Probability in Chessboard 👍

  • Time: $O(kn^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  double knightProbability(int n, int k, int row, int column) {
    constexpr int dirs[8][2] = {{1, 2},   {2, 1},   {2, -1}, {1, -2},
                                {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
    constexpr double kProb = 0.125;
    // dp[i][j] := the probability to stand on (i, j)
    vector<vector<double>> dp(n, vector<double>(n));
    dp[row][column] = 1.0;

    for (int move = 0; move < k; ++move) {
      vector<vector<double>> newDp(n, vector<double>(n));
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
          if (dp[i][j] > 0.0) {
            for (const auto& [dx, dy] : dirs) {
              const int x = i + dx;
              const int y = j + dy;
              if (x < 0 || x >= n || y < 0 || y >= n)
                continue;
              newDp[x][y] += dp[i][j] * kProb;
            }
          }
      dp = std::move(newDp);
    }

    return accumulate(dp.begin(), dp.end(), 0.0,
                      [](double subtotal, const vector<double>& row) {
      return subtotal + accumulate(row.begin(), row.end(), 0.0);
    });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public double knightProbability(int n, int k, int row, int column) {
    final int[][] dirs = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
    final double kProb = 0.125;
    // dp[i][j] := the probability to stand on (i, j)
    double[][] dp = new double[n][n];
    dp[row][column] = 1.0;

    for (int move = 0; move < k; ++move) {
      double[][] newDp = new double[n][n];
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
          if (dp[i][j] > 0.0) {
            for (int[] dir : dirs) {
              final int x = i + dir[0];
              final int y = j + dir[1];
              if (x < 0 || x >= n || y < 0 || y >= n)
                continue;
              newDp[x][y] += dp[i][j] * kProb;
            }
          }
      dp = newDp;
    }

    return Arrays.stream(dp).flatMapToDouble(Arrays::stream).sum();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def knightProbability(self, n: int, k: int, row: int, column: int) -> float:
    dirs = ((1, 2), (2, 1), (2, -1), (1, -2),
            (-1, -2), (-2, -1), (-2, 1), (-1, 2))
    # dp[i][j] := the probability to stand on (i, j)
    dp = [[0] * n for _ in range(n)]
    dp[row][column] = 1.0

    for _ in range(k):
      newDp = [[0] * n for _ in range(n)]
      for i in range(n):
        for j in range(n):
          for dx, dy in dirs:
            x = i + dx
            y = j + dy
            if 0 <= x < n and 0 <= y < n:
              newDp[i][j] += dp[x][y]
      dp = newDp

    return sum(map(sum, dp)) / 8**k