class Solution {
 public:
  double knightProbability(int N, int K, int r, int c) {
    constexpr double kProb = 0.125;
    const vector<pair<int, int>> dirs{{-2, 1}, {-1, 2}, {1, 2},   {2, 1},
                                      {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

    // dp[i][j] := probability to stand on (i, j)
    vector<vector<double>> dp(N, vector<double>(N));
    dp[r][c] = 1.0;

    for (int k = 0; k < K; ++k) {
      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 = move(newDp);
    }

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

class Solution {
  public double knightProbability(int N, int K, int r, int c) {
    final double kProb = 0.125;
    final int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

    // dp[i][j] := probability to stand on (i, j)
    double[][] dp = new double[N][N];
    dp[r][c] = 1.0;

    for (int k = 0; k < K; ++k) {
      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;
    }

    double ans = 0.0;

    for (double[] row : dp)
      ans += Arrays.stream(row).sum();

    return ans;
  }
}

class Solution:
  def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
    dirs = [(1, 2), (2, 1), (2, -1), (1, -2),
            (-1, -2), (-2, -1), (-2, 1), (-1, 2)]

    # dp[i][j] := probability to stand on (i, j)
    dp = [[0] * N for _ in range(N)]
    dp[r][c] = 1

    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