LeetCode 688. “马”在棋盘上的概率（DP）

示例：
输入: 3, 2, 0, 0
输出: 0.0625
解释: 
输入的数据依次为 N, K, r, c
第 1 步时，有且只有 2 种走法令 “马” 
可以留在棋盘上（跳到（1,2）或（2,1））。
对于以上的两种情况，各自在第2步均有且只有2种走法令 “马” 仍然留在棋盘上。
所以 “马” 在结束后仍在棋盘上的概率为 0.0625。
 
注意：
N 的取值范围为 [1, 25]
K 的取值范围为 [0, 100]
开始时，“马” 总是位于棋盘上

class Solution {
public:
    double knightProbability(int N, int K, int r, int c) {
        vector<vector<vector<double>>> dp(N, vector<vector<double>>(N, vector<double>(K+1, 0.0)));
        dp[r][c][K] = 1.0;
        vector<vector<int>> dir = {{2,1},{1,2},{-2,1},{-1,2},{2,-1},{1,-2},{-1,-2},{-2,-1}};
        int i, j, k, x, y, d;
        for(k = K; k > 0; k--) 
        {
            for(i = 0; i < N; i++)
            {
                for(j = 0; j < N; j++)
                {
                    for(d = 0; d < 8; d++)
                    {
                        x = i + dir[d][0];
                        y = j + dir[d][1];
                        if(x>=0 && x<N && y>=0 && y<N)
                        {
                            dp[x][y][k-1] += dp[i][j][k]/8.0;
                        }
                    }
                }
            }
        }
        double ans = 0.0;
        for(i = 0; i < N; i++)
            for(j = 0; j < N; j++)
                ans += dp[i][j][0];
        return ans;
    }
};