设为首页 加入收藏

TOP

Knight Probability in Chessboard“编程题”
2017-12-23 06:06:49 】 浏览:37
Tags:Knight Probability Chessboard 编程

题目描述

这里写图片描述

解题思路

题目大意如下:一个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); } };
     
    
   
  

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇c++三种继承方式讲解 下一篇c++实现插入排序(代码教程)

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目