♞ 牛局长的“迷你马”实验

（兔猫信奥学院 · 牛局长 × 闪电 × 豹警官 × 朱迪 × 尼克）

故事背景

安全局的 牛局长 带来一块 $n\times n$ 的国际象棋棋盘和一枚小巧的骑士棋子（学院同学昵称“迷你马”）。骑士起始于格子 $\bigl(row,;column\bigr)$，接下来要随机地走 $k$ 步：

• 每一步从 8 种“日”字走法中 等概率 任选一种，即便它会跳出棋盘。
• 一旦骑士跳出边界，试验立即停止；否则继续，直到走满 $k$ 步。

牛局长要求统计：

试验结束时骑士仍然留在棋盘上的概率。

闪电负责摇骰子，朱迪和尼克记录结果，豹警官在一旁护卫——真正的计算任务，就交给你啦！

题目描述

给定整数

• 棋盘边长 $n$（$1\le n\le25$），
• 试验步数 $k$（$0\le k\le100$），
• 起点坐标 $\bigl(row,;column\bigr)$（$0\le row,;column<n$）

计算骑士在走完 $k$ 步后仍位于棋盘内的概率。误差 $\le10^{-5}$ 视为正确。

输入格式

n k
row column

输出格式

probability

• probability —— 双精度结果，建议 printf("%.10f", …)。

样例

算法提示

动态规划 / 概率转移：

1. dp[s][i][j] = 骑士走完 s 步后位于 (i,j) 的概率。
2. 转移：dp[s+1][x][y] = Σ dp[s][i][j] / 8，枚举 8 个合法来源格。
3. 答案 Σ dp[k][i][j]，即第 k 步全部在盘内的概率。 可滚动数组将空间降至 O(n²)；总复杂度 O(k·n²)。