AT_abc363_e [ABC363E] Sinking Land Solution

题目大意：

有一座矩形岛屿，被分为 \(H\times W\) 的网格，四周与海水接触，给定时间 \(Y\) 年，最初海平面位于高度 \(0\ \text{m}\)，每年海水上升 \(1\ \text{m}\)，请求出每年未被海水淹没的格子数（高度小于等于海水高度即为淹没）。

显然有点类似于广搜的想法，用一个队列存储与海水接触的方块，如果当前方块高度小于等于海平面，那么此处标记为淹没，然后把四周未被淹没的方块加入队列，但是因为是队列，所以枚举队列中高度低于海平面的元素是 \(O(n)\) 的，所以使用小根堆，即优先队列，每次取出其中最小的元素，如果这个元素高度已经大于了海平面，那么就退出，可以下一年了。

由于每个元素只会进队一次，出队一次，所以时间复杂度大约是 \(O(n\log n)\) 的。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int H, W, Q, A[N][N];
bool vis[N][N];
priority_queue<pair<int, pair<int, int> > > pq;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int main() {
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> H >> W >> Q;
	for (int i = 1; i <= H; i ++) {
		for (int j = 1; j <= W; j ++) {
			cin >> A[i][j];
			if (i == 1 || i == H || j == 1 || j == W) {
				pq.push(make_pair(-A[i][j], make_pair(i, j)));
				vis[i][j] = 1;
			}
		}
	}
	int Ans = H * W;
	for (int k = 1; k <= Q; k ++) {
		while (!pq.empty() && -pq.top().first <= k) {
			Ans --; int x = pq.top().second.first, y = pq.top().second.second;
			pq.pop();
			for (int i = 0; i < 4; i ++) {
				int nxtx = x + dx[i], nxty = y + dy[i];
				if (nxtx >= 1 && nxtx <= H && nxty >= 1 && nxty <= W && !vis[nxtx][nxty])
					pq.push(make_pair(-A[nxtx][nxty], make_pair(nxtx, nxty))), vis[nxtx][nxty] = 1;
			}
		}
		cout << Ans << "\n";
	}
	return 0;
}