最简单思路，没有之一

解题思路:拿到这道题，看一下题意与数据规模，暴力肯定过不了，但这里我们不妨想想暴力是怎么写的，其实就是对每个结点进行dfs嘛，查找它能到的所有结点中最大的那个返回，然后求和最后除以结点数量对吧？那确实，但暴力写法我试了试只能拿73分，也挺高了。那么这道题的正确思路是什么呢？其实很简单，暴力思路为啥过不了？那是因为它每个点都要dfs一下，及其耗时间。那么优化思路就出来了，我们有必要对所有结点都dfs吗？根据题意不难发现，假设我从某个结点出发，能到达的所有结点他们的dfs结果是相同的，这个其实很容易发现，因为根据题目规则，每一条合法路径实际就是一个无向图，大家不妨自己试一下。ok，知道了这个，这题基本已经解决了，我们不妨用并查集合并这些相同dfs的点，构成若干个集合，每个集合我们只对它的代表结点进行dfs，这样就大大加快了时间，假如说总结点数目为N，实测下来时间复杂度不超过o（NlogN），甚至更低。

注意事项:

1. 二维的数组用并查集合并结点的话通常是压成一维数组求ID来代表原来二维数组中各个位置的结点

2. 由于我们对每个集合的处理是只对它的代表结点进行dfs，而每个集合算出来的结果应该是dfs乘以该集合的大小，因此还需要一个size数组来统计每个集合的大小
   参考代码:

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n, m;

vector<ll> h;          // 高度

vector<int> fa, sz;    // 并查集

vector<char> vis;      // DFS 访问标记（一次 DFS 内使用）

inline int id(int x, int y) {

    return x * m + y;

}

int find(int x) {

    return x == fa[x] ? x : fa[x] = find(fa[x]);

}

void unite(int a, int b) {

    a = find(a);

    b = find(b);

    if (a == b) return;

    fa[b] = a;

    sz[a] += sz[b];

}

ll dfs(int u) {

    vis[u] = 1;

    ll best = h[u];

    int x = u / m;

    int y = u % m;

    // 1) 向下：行增大，高度更小

    for (int i = x + 1; i < n; i++) {

        int v = id(i, y);

        if (h[v] < h[u] && !vis[v]) {

            unite(u, v);

            best = max(best, dfs(v));

        }

    }

    // 2) 向上：行减小，高度更大

    for (int i = 0; i < x; i++) {

        int v = id(i, y);

        if (h[v] > h[u] && !vis[v]) {

            unite(u, v);

            best = max(best, dfs(v));

        }

    }

    // 3) 向右：列增大，高度更小

    for (int j = y + 1; j < m; j++) {

        int v = id(x, j);

        if (h[v] < h[u] && !vis[v]) {

            unite(u, v);

            best = max(best, dfs(v));

        }

    }

    // 4) 向左：列减小，高度更大

    for (int j = 0; j < y; j++) {

        int v = id(x, j);

        if (h[v] > h[u] && !vis[v]) {

            unite(u, v);

            best = max(best, dfs(v));

        }

    }

    return best;

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin >> n >> m;

    int N = n * m;

    h.resize(N);

    fa.resize(N);

    sz.resize(N);

    vis.resize(N);

    for (int i = 0; i < N; i++) {

        cin >> h[i];

        fa[i] = i;

        sz[i] = 1;

    }

    double ans = 0.0;

    for (int i = 0; i < N; i++) {

        if (find(i) != i) continue; // 已经被合并过

        fill(vis.begin(), vis.end(), 0);

        ll mx = dfs(i);

        int root = find(i);

        ans += (double)sz[root] * mx;

    }

    cout << fixed << setprecision(6)

         << ans / N << "\n";

    return 0;

}