Knight Probability in Chessboard 编程题

    选择打赏方式

    题目描述:

6R5Z2_`8FP5TQV`O65{T_]6.png


    解题思路:

题目大意如下:一个N*N的棋盘,给定一个骑士的初始位置(r,c),再给一个步数限制K,表示这个骑士刚好可以走K步(每一步有8种走法,即“日”字型走法),问走过K步后还在棋盘内的可能。

这道题目和out of boundary path有异曲同工之处,因为每一步都有8种走法,那么K步就有8^K种可能,而我们只需要找出在这8^K种可能里有多少种是还未走出边界的,解法类似,但这里为了节省空间,少掉一个维度,即将步数视为一个时间维度,每走一次,dp[i][j]就更新一次,而每次更新之前,都需一个temp[i][j]来记录走这一次之后的没走出边界的情况总和,循环棋盘上的每个位置之后再赋值给dp[i][j]。

    代码实现:

class Solution {
public:
    double knightProbability(int N, int K, int r, int c) {
        if (K == 0) return 1;
        vector<vector<double> > dp(N, vector<double>(N, 1));
        int move[8][2] = {{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
        for (int k = 0; k < K; ++k) {
            vector<vector<double> > t(N, vector<double>(N, 0));
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N; ++j) {
                    for (int m = 0; m < 8; ++m) {
                        int x = i + move[m][0], y = j + move[m][1];
                        if (x >= 0 && x <= N-1 && y >= 0 && y <= N-1)
                            t[i][j] += dp[x][y];
                    }
                }
            }
            dp = t;
        }
        return dp[r][c] / pow(8, K);
    }
};</double></vector<double></double></vector<double>
版权声明:若无特殊注明,本文皆为《 IT盒子-ITBoxs 》原创,转载请保留文章出处。
本文链接:Knight Probability in Chessboard 编程题 https://www.itboxs.cn/?post=188
正文到此结束

热门推荐

发表吐槽

你肿么看?

你还可以输入 250 / 250 个字

嘻嘻 大笑 可怜 吃惊 害羞 调皮 鄙视 示爱 大哭 开心 偷笑 嘘 奸笑 委屈 抱抱 愤怒 思考 日了狗 胜利 不高兴 阴险 乖 酷 滑稽

评论信息框

吃奶的力气提交吐槽中...


既然没有吐槽,那就赶紧抢沙发吧!