当前位置： 移动技术网 > IT编程>开发语言>C/C++ > Knight Probability in Chessboard“编程题”

Knight Probability in Chessboard“编程题”

2018年01月02日  | 移动技术网IT编程  | 我要评论

刘羽琦整容前,山西社区,尘肺病分为几期

题目描述

这里写图片描述

解题思路

题目大意如下：一个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]。

C++代码实现

class Solution {
public:
    double knightProbability(int N, int K, int r, int c) {
        if (K == 0) return 1;
        vector > dp(N, vector(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 > t(N, vector(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);
    }
};

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网