PBCWATER - Tính toán lượng nước
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 100, d[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}, INF = 1e9;
int h[N][N], f[N][N], m, n;
pair<int, pair<int, int> > a[N*N];
void enter() {
cin >> m >> n;
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
cin >> h[i][j], a[i*n+j] = make_pair(h[i][j], make_pair(i, j));
}
void solve() {
memset(f, -1, sizeof f);
sort(a, a+m*n);
for(int i = 0; i < m*n; ++i) {
int x = a[i].second.first, y = a[i].second.second;
queue<pair<int, int> > q;
if(x==0 || x==m-1 || y==0 || y==n-1 || f[x-1][y]!=-1 || f[x+1][y]!=-1 || f[x][y-1]!=-1 || f[x][y+1]!=-1)
f[x][y] = h[x][y], q.push(make_pair(x, y));
while(!q.empty()) {
int x = q.front().first, y = q.front().second; q.pop();
for(int k = 0; k < 4; ++k) {
int u = x + d[k][0], v = y + d[k][1];
if(u >= 0 && u < m && v >= 0 && v < n && h[u][v] <= f[x][y] && f[u][v] == -1)
f[u][v] = f[x][y], q.push(make_pair(u, v));
}
}
}
}
void print() {
int res = 0;
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
res += f[i][j] - h[i][j];
cout << res << endl;
}
int main() {
ios::sync_with_stdio(false);
enter();
solve();
print();
return 0;
}