0688. Knight Probability in Chessboard

题目信息

题号:

0688

难度:

Medium

主题:

棋盘、骑士随机移动、越界吸收、概率

原题:

LeetCode 0688

重点:

每一步从八种骑士走法中等概率选择、越界后不再返回棋盘、求恰好执行 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。