problem: https://leetcode.com/problems/knight-probability-in-chessboard/
This is an easy problem using dfs.
class Solution { public: vector<int> dx{1,2,2,1,-1,-2,-2,-1}; vector<int> dy{2,1,-1,-2,-2,-1,1,2}; vector<vector<vector<double>>> dp; double knightProbability(int N, int K, int r, int c) { double res = 0.0; if(K == 0) return 1.0; if(dp.empty()) { dp.resize(K + 1, vector<vector<double>>(N, vector<double>(N, -1))); } if(dp[K][r][c] != -1) return dp[K][r][c]; for(int k = 0;k < 8 ;k++) { int x = r + dx[k]; int y = c + dy[k]; if(x >= 0 && x < N && y >= 0 && y < N) { res += knightProbability(N, K - 1, x, y) * 0.125; } } return dp[K][r][c] = res; } };
转载于:https://www.cnblogs.com/fish1996/p/11371026.html
相关资源：JAVA上百实例源码以及开源项目