木桶原理,缩圈题
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
struct Node { // use struct as value
int x, y;
int val;
friend bool const operator<(const Node &a, const Node &b) {
return a.val > b.val;
}
};
int a[N][N];
bool st[N][N];
int main() {
int T; cin >> T;
priority_queue<Node> q;
for (int t = 1; t <= T; t++) {
memset(st, false, sizeof st);
q = {}; // 解锁重置stl的新大门
int ans = 0;
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> a[i][j];
for (int i = 1; i < m-1; i++) q.push(Node{0, i, a[0][i]}), q.push(Node{n-1, i, a[n-1][i]}), st[0][i] = st[n-1][i] = true;
for (int i = 1; i < n-1; i++) q.push(Node{i, 0, a[i][0]}), q.push(Node{i, m-1, a[i][m-1]}), st[i][0] = st[i][m-1] = true;
st[0][0] = st[0][m-1] = st[n-1][0] = st[n-1][m-1] = true;
while (!q.empty()) {
auto t = q.top(); q.pop();
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
for (int i = 0; i < 4; i++) {
int x = t.x + dx[i], y = t.y + dy[i];
if (st[x][y] || x < 0 || x >= n || y < 0 || y >= m) continue;
if (a[x][y] < t.val) ans += t.val - a[x][y];
q.push(Node{x, y, max(a[x][y], t.val)}), st[x][y] = true;
}
}
printf("Case #%d: %d\n", t, ans);
}
return 0;
}