随机滑行的期望代价

题目描述

雪橇手在冰原上滑行，冰原被划成 $n\times m$ 的格子，每个格子有不同的摩擦代价。雪橇手从左上角 $(1,1)$ 出发，尚未抵达右下角 $(n,m)$ 时，每一步都会以等概率选择“向右”或“向下”滑行（若某个方向越界，则必然选择另一方向）。滑过某格子会累加对应代价。请计算雪橇手抵达终点的期望总代价。

输入格式

第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含 $m$ 个整数，表示各格子的摩擦代价。

输出格式

输出一个实数，表示期望总代价。允许误差不超过 $10^{-6}$。

输入输出样例 #1

输入 #1

2 2
1 2
3 4

输出 #1

7.500000

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 500$，代价满足 $0 \le w_{i,j} \le 10^4$。EOF