leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0688.cpp (740B)

0 class Solution { 1 bool valid(int n, int x, int y) { return x >= 0 && y >= 0 && x < n && y < n; } 2 3 double dp[25][25][101]; 4 5 public: 6 double knightProbability(int n, int k, int row, int column) { 7 static const int offset_x[] = {-2, -2, -1, 1, 2, 2, 1, -1}; 8 static const int offset_y[] = {-1, 1, 2, 2, 1, -1, -2, -2}; 9 10 if (!k) return 1; 11 if (dp[row][column][k]) return dp[row][column][k]; 12 13 double res = 0; 14 for (int i = 0; i < 8; i++) { 15 int x = row + offset_x[i]; 16 int y = column + offset_y[i]; 17 18 if (!valid(n, x, y)) continue; 19 res += 0.125 * knightProbability(n, k - 1, x, y); 20 }; 21 22 return dp[row][column][k] = res; 23 } 24 };