#include <bits/stdc++.h> using namespace std; typedef long long int ll; struct Hasher { ll operator() (const pair<ll, ll>& Key) const { return (Key.first<<31) | Key.second; } }; unordered_map<pair<ll, ll>, bool, Hasher> Board; unordered_map<pair<ll, ll>, pair<int, int>, Hasher> Walls; unordered_map<pair<ll, ll>, bool, Hasher> visited; int Solve() { queue<pair<int, int>> Q; for(auto e : Board) { auto [x, y] = e.first; if(Board.find({x, y-1}) != Board.end()) Walls[{x, y}].first++; if(Board.find({x+1, y}) != Board.end()) Walls[{x, y}].second++; if(Board.find({x, y+1}) != Board.end()) Walls[{x, y}].first++; if(Board.find({x-1, y}) != Board.end()) Walls[{x, y}].second++; if(Walls[{x, y}].first == 0 || Walls[{x, y}].second == 0) { Q.push({x, y}); visited[{x, y}] = true; } } int sol = 0; while(!Q.empty()) { auto [x, y] = Q.front(); Q.pop(); sol++; if(Board.find({x, y-1}) != Board.end()) { Walls[{x, y-1}].first--; if(!visited[{x, y-1}] && Walls[{x, y-1}].first == 0) { Q.push({x, y-1}); visited[{x, y-1}] = true; } } if(Board.find({x+1, y}) != Board.end()) { Walls[{x+1, y}].second--; if(!visited[{x+1, y}] && Walls[{x+1, y}].second == 0) { Q.push({x+1, y}); visited[{x+1, y}] = true; } } if(Board.find({x, y+1}) != Board.end()) { Walls[{x, y+1}].first--; if(!visited[{x, y+1}] && Walls[{x, y+1}].first == 0) { Q.push({x, y+1}); visited[{x, y+1}] = true; } } if(Board.find({x-1, y}) != Board.end()) { Walls[{x-1, y}].second--; if(!visited[{x-1, y}] && Walls[{x-1, y}].second == 0) { Q.push({x-1, y}); visited[{x-1, y}] = true; } } } visited.clear(); Walls.clear(); return sol; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m, k, q, x, y; cin >> n >> m >> k >> q; for(int i = 0; i < k; i++) { cin >> x >> y; Board[{x, y}] = 1; } cout << Solve() << "\n"; for(int i = 0; i < q; i++) { cin >> x >> y; if(Board.find({x, y}) != Board.end()) Board.erase({x, y}); else Board[{x, y}] = 1; cout << Solve() << "\n"; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | #include <bits/stdc++.h> using namespace std; typedef long long int ll; struct Hasher { ll operator() (const pair<ll, ll>& Key) const { return (Key.first<<31) | Key.second; } }; unordered_map<pair<ll, ll>, bool, Hasher> Board; unordered_map<pair<ll, ll>, pair<int, int>, Hasher> Walls; unordered_map<pair<ll, ll>, bool, Hasher> visited; int Solve() { queue<pair<int, int>> Q; for(auto e : Board) { auto [x, y] = e.first; if(Board.find({x, y-1}) != Board.end()) Walls[{x, y}].first++; if(Board.find({x+1, y}) != Board.end()) Walls[{x, y}].second++; if(Board.find({x, y+1}) != Board.end()) Walls[{x, y}].first++; if(Board.find({x-1, y}) != Board.end()) Walls[{x, y}].second++; if(Walls[{x, y}].first == 0 || Walls[{x, y}].second == 0) { Q.push({x, y}); visited[{x, y}] = true; } } int sol = 0; while(!Q.empty()) { auto [x, y] = Q.front(); Q.pop(); sol++; if(Board.find({x, y-1}) != Board.end()) { Walls[{x, y-1}].first--; if(!visited[{x, y-1}] && Walls[{x, y-1}].first == 0) { Q.push({x, y-1}); visited[{x, y-1}] = true; } } if(Board.find({x+1, y}) != Board.end()) { Walls[{x+1, y}].second--; if(!visited[{x+1, y}] && Walls[{x+1, y}].second == 0) { Q.push({x+1, y}); visited[{x+1, y}] = true; } } if(Board.find({x, y+1}) != Board.end()) { Walls[{x, y+1}].first--; if(!visited[{x, y+1}] && Walls[{x, y+1}].first == 0) { Q.push({x, y+1}); visited[{x, y+1}] = true; } } if(Board.find({x-1, y}) != Board.end()) { Walls[{x-1, y}].second--; if(!visited[{x-1, y}] && Walls[{x-1, y}].second == 0) { Q.push({x-1, y}); visited[{x-1, y}] = true; } } } visited.clear(); Walls.clear(); return sol; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m, k, q, x, y; cin >> n >> m >> k >> q; for(int i = 0; i < k; i++) { cin >> x >> y; Board[{x, y}] = 1; } cout << Solve() << "\n"; for(int i = 0; i < q; i++) { cin >> x >> y; if(Board.find({x, y}) != Board.end()) Board.erase({x, y}); else Board[{x, y}] = 1; cout << Solve() << "\n"; } } |