计算归途

核心撷取了，但回家的路还有一段——一段需要计算的归途。

"归途？"CC问。

"对。"你说，"一个探测球，在网格上移动。每次可以上下左右走，但有些地方是陷阱，会掉下去。"

"陷阱？"

"对。"你说，"每个格子有一个概率$p_{ij}$，表示安全通过的概率。"

"目标？"

"从起点到终点，求成功到达的期望步数。"

"期望步数？"

"对。"你说，"如果掉下去，回到起点，重新走。"

"咋算？"

"动态规划。"你说，"设$E[i][j]$为从$(i,j)$到终点的期望步数。"

"转移？"

"对。"你说，"$E[i][j]=1+p_{avg}\times average(E[next])+(1-p_{ij})\times E[start]$。"

"复杂。"

"对。"你说，"但可以用高斯消元或迭代法解。"

"第47格。"你说，"$(4,7)$——安全概率0.47。"

"危险。"

"对。"你说，"但可以通过。"

"咋过？"

"绕路。"你说，"或者硬闯——期望告诉我们，闯多少次能过。"

CC看着归途——像一条线，像一条河，像某种必须走但又充满危险的路。

"能回家吗？"她问。

"能。"你说，"期望告诉我们，能。"

"多久？"

"算出来就知道了。"你说，"但肯定会到。"

Echo把归途的地图投射出来——弯弯曲曲，但终点是亮的。

"以前我不敢走。"她说，"怕掉下去。"

"现在呢？"

"现在走了。"她说，"因为你们在终点等我。"

题目描述

$n\times m$网格，每个格子安全概率$p_{ij}$。从起点走到终点，上下左右移动。掉入陷阱则回到起点。求到达终点的期望步数。

输入格式

第一行$n,m$。接下来$n$行，每行$m$个实数。

输出格式

期望步数，保留3位小数。

输入样例

5

输出样例

0.00

提示

• 设$E[i][j]$为从$(i,j)$到终点的期望步数。
• 建立线性方程组，高斯消元或迭代求解。
• 注意边界条件：$E[end]=0$。