C11WATER - Đọng nước
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int N = 1010;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int oo = 1000000009;
using namespace std;
int d[N][N], a[N][N];
int m, n;
int main() {
scanf("%d %d", &m, &n);
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &a[i][j]), d[i][j] = oo;
priority_queue<iii, vector<iii>, greater<iii> > Q;
for(int i = 1; i <= m; i++) {
d[i][1] = a[i][1]; d[i][n] = a[i][n];
Q.push(iii(a[i][1], ii(i, 1)));
Q.push(iii(a[i][n], ii(i, n)));
}
for(int i = 2; i < n; i++) {
d[1][i] = a[1][i]; d[m][i] = a[m][i];
Q.push(iii(a[1][i], ii(1, i)));
Q.push(iii(a[m][i], ii(m, i)));
}
while (!Q.empty()) {
ii u = Q.top().Y; int du = Q.top().X; Q.pop();
if (du != d[u.X][u.Y]) continue;
for(int i = 0; i < 4; i++) {
ii v (u.X + dx[i], u.Y + dy[i]);
if (v.X < 1 || v.Y < 1 || v.X > m || v.Y > n) continue;
if (d[v.X][v.Y] > max(d[u.X][u.Y], a[v.X][v.Y])) {
d[v.X][v.Y] = max(d[u.X][u.Y], a[v.X][v.Y]);
Q.push(iii(d[v.X][v.Y], v));
}
}
}
long long res = 0;
for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++)
if (d[i][j] > a[i][j]) res += d[i][j] - a[i][j];
printf("%lld", res);
return 0;
}