题解 | 晶体能量阱储量计算

#include <bits/stdc++.h>
using namespace std;

const int N = 305;
const int inf = 0x3f3f3f3f;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int m, n, e[N][N];
int edx, edy, dist[N][N];
bool st[N][N];

struct node {
    int dis, x, y;
    bool operator < (const node & t) const {
		return this -> dis > t.dis;
	}
};

void dij() {
    memset(dist, 0x3f, sizeof dist);
    priority_queue<node>q;
    for(int i=1; i<=m; i++) q.push({0,0,i}), q.push({0,n+1,i});
    for(int i=1; i<=n; i++) q.push({0,i,0}), q.push({0,i,m+1});
    while( q.size() ) {
        auto [dis, nowx, nowy] = q.top();
        q.pop();
        // cout << "x = " << nowx << " y = " << nowy << endl;
        if(st[nowx][nowy]) continue;
        st[nowx][nowy] = true;
        for(int i=0; i<4; i++) {
            int tx = nowx + dx[i], ty = nowy + dy[i];
            if(tx<1||tx>n||ty<1||ty>m) continue;
            int d = max(dis, e[tx][ty]);
            if(dist[tx][ty] > d) {
                dist[tx][ty] = d;
                q.push({d, tx, ty});
            }
        }
    }
}

int main() {
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> m >> n;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> e[i][j];
        }
    }
    dij();
    int res = 0;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            res += max(0, dist[i][j] - e[i][j]); // dist(i,j)一定大于等于e(i,j)可以不用max
            // cout << "i = " << i << " j = " << j << " dis = " << dist[i][j] << endl;
        }
    }
    cout << res;
    return 0;
}
// 64 位输出请用 printf("%lld")

观察到能使用dijkstra从终点即外面一圈的点出发计算每个点的逃逸势能