P12169 [蓝桥杯 2025 省 C/Python A/Java C] 登山

小蓝正在登山，山峰的高度构成 $n$ 行 $m$ 列的正整数矩阵，$a_{i,j}$ 表示第 $i$ 行第 $j$ 列格子 $(i,j)$ 上的山峰的高度。小蓝以一种特别的方式进行登山，如果他此刻在第 $p$ 行第 $q$ 列的格子 $(p,q)$ 上，那么下一步可以选择： 1. 走到格子 $(i,q)$，满足 $a_{i,q} < a_{p,q}$ 且 $i > p$； 2. 走到格子 $(i,q)$，满足 $a_{i,q} > a_{p,q}$ 且 $i < p$； 3. 走到格子 $(p,j)$，满足 $a_{p,j} < a_{p,q}$ 且 $j > q$； 4. 走到格子 $(p,j)$，满足 $a_{p,j} > a_{p,q}$ 且 $j < q$。 小蓝想知道，如果他依次从每一个格子开始出发，按照最优策略，他最高能到达的山峰的高度的平均值是多少？

输入的第一行包含两个正整数 $n, m$，用一个空格分隔。 接下来 $n$ 行，每行包含 $m$ 个正整数。其中第 $i$ 行包含 $a_{i,1}, a_{i,2}, \cdots, a_{i,m}$，相邻整数之间使用一个空格分隔。

输出一行包含一个实数表示答案，四舍五入保留正好 $6$ 位小数。

### 样例说明 1 除了从格子 $(1,1)$ 出发以外，其他格子都能到达高度为 $3$ 的山峰，$(1 + 3 + 3 + 3)/4 = 2.5$。 ### 样例说明 2 每个格子能到达的高度： $$\begin{matrix} 4 & 4 & 4 \\ 4 & 4 & 5\end{matrix}$$ 其中 $(1,1)$ 可以先到达格子 $(1,3)$ 再到达格子 $(1,2)$。 ### 评测用例规模与约定 - 对于 $40\%$ 的评测用例，$1 \leq n, m \leq 10^2$； - 对于所有评测用例，$1 \leq n, m \leq 10^4$，$1 \leq n \times m \leq 10^6$，$1 \leq a_{ij} \leq 10^9$。