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;
}

Download