ABC 363

E - Sinking Land我的错误做法两个队列交替nxtq用来存比当前队列里的元素高一米的元素作为下个高度的队列的元素错误点如果有一个位置不在当前队列扩展的范围但是高度满足要求就会漏掉。这个位置本应该在之前的扩展就纳入队列。#include bits/stdc.h using namespace std; using PII pairint, int; int main() { int n, m, y; cin n m y; vectorvectorint g(n 1, vectorint(m 1)), st(n 1, vectorint(m 1, 0)); queuePII q, nxtq; int h 1; int remain n * m; int minadj 1e9; for(int i 1; i n; i) { for(int j 1; j m; j) { cin g[i][j]; if(i 1 || j 1 || i n || j m) { minadj min(minadj, g[i][j]); } } } while(h minadj) { cout remain endl; h; } for(int i 1; i n; i) { for(int j 1; j m; j) { if((i 1 || j 1 || i n || j m) g[i][j] minadj) { q.push({i, j}); // cout i j ; st[i][j] 1; remain--; } } } int nxtcnt 0; vectorPII d{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while(h y) { remain - nxtcnt; nxtcnt 0; while(q.size()) { auto [X, Y] q.front(); q.pop(); for(auto [dx, dy] : d) { int x dx X, y Y dy; if(x 1 x n y 1 y m) { if(!st[x][y] g[x][y] h) { q.push({x, y}); st[x][y] 1; remain--; } if(!st[x][y] g[x][y] h 1) { nxtq.push({x, y}); st[x][y] 1; nxtcnt; } } } } cout remain endl; h; q nxtq; } }正解优先队列直接按高度排序三元组存位置{ x, y, t }, t 表示该位置在那一时刻被淹没。#include bits/stdc.h using namespace std; using TI tupleint, int, int; using PII pairint, int; int main() { int n, m, T; cin n m T; vectorvectorint g(n 1, vectorint(m 1)), st(n 1, vectorint(m 1)); auto cmp [](TI a, TI b) { auto [x, y, z] a; auto [u, v, w] b; return z w; }; priority_queueTI, vectorTI, decltype(cmp) pq(cmp); vectorint ans(T 1); for(int i 1; i n; i) { for(int j 1; j m; j) { cin g[i][j]; if(i 1 || j 1 || i n || j m) { pq.push({i, j, g[i][j]}); if(g[i][j] T) ans[g[i][j]]; st[i][j] 1; } } } vectorPII d{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while(pq.size()) { auto [X, Y, Z] pq.top(); // 第三元是被淹没的时刻 pq.pop(); for(auto [dx, dy] : d) { int x dx X; int y dy Y; if(x 1 x n y 1 y m) { if(!st[x][y] g[x][y] T) { if(g[x][y] Z) { pq.push({x, y, Z}); ans[Z]; } else { pq.push({x, y, g[x][y]}); ans[g[x][y]]; } st[x][y] 1; } } } } for(int i 1; i T; i) ans[i] ans[i - 1] ans[i]; for(int i 1; i T; i) cout n * m - ans[i] endl; }