想法

这道题感觉很综合，y总的算法有点农村包围城市的感觉
就是最外面靠海的点都入堆，然后从他们开始四个方向一个点一个点的向中心逼近
  对于每个点只用算一次就能得出最优解
计算的时候是不用考虑除了上下左右四个方向以外其他的点的，因为这是从最外边算进来的
（y总的代码dist[][]是不需要的，我也不知道y总开这个数组是拿来干嘛的）

（说真的没有感觉到有迪杰斯特拉，可能是我太菜了8

cpp代码

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
const int N = 60;
int h[N][N], book[N][N];
int Next[4][2]={0, 1, 1 , 0, 0, -1, -1, 0}; //方向向量
int n, m, T;
struct Node
{
    int x, y, d;
    bool operator < (const Node &t) const
    {
        return d > t.d;
    }
};
int main()
{
    cin >> T;
    for(int C = 1; C <= T; C ++)
    {
        cin >> n >> m;
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
                cin >> h[i][j];
        memset(book, 0, sizeof book);
        priority_queue<Node> heap;  //小根堆，每次取的都是最小值，木桶效应的短木板
        int sum = 0;
        for(int i = 1; i <= m; i ++)  //四周所有的点先入堆
            {
                heap.push({1, i, h[1][i]});
                heap.push({n, i, h[n][i]});
            }
        for(int i = 2; i <= n - 1; i ++)
            {
                heap.push({i, 1, h[i][1]});
                heap.push({i, m, h[i][m]});    
            }
        while(!heap.empty())
        {
            auto t = heap.top();  //取堆顶，也就是最小的
            heap.pop();
            if(book[t.x][t.y]) continue;
            book[t.x][t.y] = 1;
            sum += t.d - h[t.x][t.y];  // t.d就是(tx,ty)处最后水的高度
            for(int k = 0; k < 4; k ++)
            {
                int dx = t.x + Next[k][0];
                int dy = t.y + Next[k][1];
                if(dx < 1 || dx > n || dy < 1 || dy > m ) 
                    continue;
                heap.push({dx, dy, max(t.d, h[dx][dy])}); // (dx,dy)有两种情况，要么是它本身超级高
                                                        //要么它旁边的比他高(t.d)，比一下max谁高就是谁
                //由于是小根堆，因此每次拿出来的都是堆中最小值。读取到(dx,dy)这个点的时候，是从(tx,ty)过来的
                //对应的t.d就是它四周里面最小的，也就是木桶效应的短木板
            }
        }
        printf("Case #%d: %d\n", C, sum);
    }
    return 0;
}

```