蓝桥杯2025年第十六届省赛真题-登山

小蓝正在登山，山峰的高度构成 n 行 m 列的正整数矩阵，a_{i, j} 表示第 i 行 第 j 列格子 (i, j) 上的山峰的高度。小蓝以一种特别的方式进行登山，如果他此 刻在第 p 行第 q 列的格子 (p, q) 上，那么下一步可以选择： 

1) 走到格子 (i, q)，满足 a_i,q < ap,q 且 i > p ； 

2) 走到格子 (i, q)，满足 a_i,q > ap,q 且 i < p ； 

3) 走到格子 (p, j)，满足 a_{p, j} < ap,q 且 j > q ； 

4) 走到格子 (p, j)，满足 a_{p, j} > ap,q 且 j < q 。 

小蓝想知道，如果他依次从每一个格子开始出发，按照最优策略，他最高 能到达的山峰的高度的平均值是多少？

输入的第一行包含两个正整数 n, m ，用一个空格分隔。 

接下来 n 行，每行包含 m 个正整数。其中第 i 行包含 a_i,1, a_i,2, · · · , a_i,m ，相 邻整数之间使用一个空格分隔。

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

2 2
1 3
3 2

2.500000

【样例说明 1】 

除了从格子 (1, 1) 出发以外，其他格子都能到达高度为 3 的山峰，(1 + 3 + 3 + 3)/4 = 2.5 。 

【样例输入 2】

 2 3 2 4 1 4 2 5 

【样例输出 2】 

4.166667 

【样例说明 2】 

每个格子能到达的高度： 

4, 4, 4 

4, 4, 5 

其中 (1, 1) 可以先到达格子 (1, 3) 再到达格子 (1, 2) 。 

【评测用例规模与约定】 

对于 40% 的评测用例，1 ≤ n, m ≤ 10² ； 

对于所有评测用例，1 ≤ n, m ≤ 10⁴ ，1 ≤ n × m ≤ 10⁶ ，1 ≤ ai j ≤ 10⁹ 。