0688. Knight Probability in Chessboard¶
题目信息¶
- 题号:
0688
- 难度:
Medium
- 主题:
棋盘、骑士随机移动、越界吸收、概率
- 原题:
- 重点:
每一步从八种骑士走法中等概率选择、越界后不再返回棋盘、求恰好执行 k 步后仍在棋盘内的概率
题目重述¶
在 n × n 棋盘上,骑士从零基位置 (row, column) 出发。每一步都从八种标准骑士移动中等概率选择一种,即横向移动 2 格并纵向移动 1 格,或纵向移动 2 格并横向移动 1 格,各方向符号任意。
若某一步落到棋盘外,骑士离开棋盘且之后不会重新进入。返回恰好执行 k 步后骑士仍位于棋盘内的概率。n 位于 [1, 25],k 位于 [0, 100],起点保证在棋盘内。
自建示例¶
中心位置一步后全部越界:
输入:n = 3,k = 1,row = 1,column = 1
输出:0.0
解释:在 3×3 棋盘中心,八种骑士落点都位于棋盘外,因此一步后留在棋盘内的概率为 0。
角落只有两个合法落点:
输入:n = 4,k = 1,row = 0,column = 0
输出:0.25
解释:八种等概率移动中只有 (1,2) 和 (2,1) 留在棋盘内,因此概率为 2/8=0.25。