688. Knight Probability in Chessboard

    vector<pair<int,int>> moves = {{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-1,2},{-2,1}};
    double moving(int N, int K, int r, int c, vector<vector<vector<double>>>& pk) {
        if(r<0 || r>=N || c<0 || c>=N) return 0.;
        if(K == 0) {
            return 1.;
        }
        if(pk[r][c][K-1] != 0)
            return pk[r][c][K-1];
        for(int i=0; i<8; i++) {
            pk[r][c][K-1] += moving(N, K-1, r+moves[i].first, c+moves[i].second, pk)/8.;
        }
        return pk[r][c][K-1];
    }
    double knightProbability(int N, int K, int r, int c) {
        if(K == 0) return 1.;
        vector<vector<vector<double>>> pk(N, vector<vector<double>> (N, vector<double> (K, 0.)));
        return moving(N, K, r, c, pk);
    }