#include <bits/stdc++.h> using namespace std; set<pair<int, int>> klocki; map<pair<int, int>, pair<pair<bool, bool>, pair<bool, bool>>> usun; // ((x + 1, y) (x - 1, y)) ((x, y + 1), (x, y - 1)) void fill(queue<pair<int, int>>& q) { // cerr << "start:\n"; for (auto k: klocki) { int x = k.first, y = k.second; usun[k] = {{klocki.find({x + 1, y}) == klocki.end(), klocki.find({x - 1, y}) == klocki.end()}, {klocki.find({x, y + 1}) == klocki.end(), klocki.find({x, y - 1}) == klocki.end()}}; if (usun[k].first == make_pair(true, true) || usun[k].second == make_pair(true, true)) { q.push(k); // cerr << "wrzucam " << k.first << " " << k.second << "\n"; } } } int bfs(queue<pair<int, int>>& q) { int ile = 0; while (!q.empty()) { // { pair<int, int> k = q.front(); // cerr << "przetwarzam " << k.first << " " << k.second << "\n"; int x = k.first, y = k.second; q.pop(); ile++; if (klocki.find({x - 1, y}) != klocki.end()) { usun[{x - 1, y}].first.first = 1; if (usun[{x - 1, y}].first == make_pair(true, true) && usun[{x - 1, y}].second != make_pair(true, true)) { q.push({x - 1, y}); // cerr << "wrzucam " << x - 1 << " " << y << "\n"; } } if (klocki.find({x + 1, y}) != klocki.end()) { usun[{x + 1, y}].first.second = 1; if (usun[{x + 1, y}].first == make_pair(true, true) && usun[{x + 1, y}].second != make_pair(true, true)) { q.push({x + 1, y}); // cerr << "wrzucam " << x + 1 << " " << y << "\n"; } } if (klocki.find({x, y - 1}) != klocki.end()) { usun[{x, y - 1}].second.first = 1; if (usun[{x, y - 1}].second == make_pair(true, true) && usun[{x, y - 1}].first != make_pair(true, true)) { q.push({x, y - 1}); // cerr << "wrzucam " << x << " " << y - 1 << "\n"; } } if (klocki.find({x, y + 1}) != klocki.end()) { usun[{x, y + 1}].second.second = 1; if (usun[{x, y + 1}].second == make_pair(true, true) && usun[{x, y + 1}].first != make_pair(true, true)) { q.push({x, y + 1}); // cerr << "wrzucam " << x << " " << y + 1 << "\n"; } } } return ile; } int check() { queue<pair<int, int>> q; fill(q); return bfs(q); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k, q; cin >> n >> m >> k >> q; for (int i = 0; i < k; i++) { int x, y; cin >> x >> y; klocki.insert({x, y}); } int out = check(); cout << out << "\n"; for (int i = 0; i < q; i++) { int x, y; cin >> x >> y; auto it = klocki.find({x, y}); if (it != klocki.end()) { klocki.erase(it); // jeśli usuwam coś, co i tak byłoby usunięte if (usun[{x, y}].first == make_pair(true, true) || usun[{x, y}].second == make_pair(true, true)) { out--; } else { queue<pair<int, int>> queue; queue.push({x, y}); out += bfs(queue) - 1; } } else { klocki.insert({x, y}); usun[{x, y}] = {{klocki.find({x + 1, y}) == klocki.end(), klocki.find({x - 1, y}) == klocki.end()}, {klocki.find({x, y + 1}) == klocki.end(), klocki.find({x, y - 1}) == klocki.end()}}; if (usun[{x, y}].first == make_pair(true, true) || usun[{x, y}].second == make_pair(true, true)) { out++; } else { out = check(); } } cout << out << "\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 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | #include <bits/stdc++.h> using namespace std; set<pair<int, int>> klocki; map<pair<int, int>, pair<pair<bool, bool>, pair<bool, bool>>> usun; // ((x + 1, y) (x - 1, y)) ((x, y + 1), (x, y - 1)) void fill(queue<pair<int, int>>& q) { // cerr << "start:\n"; for (auto k: klocki) { int x = k.first, y = k.second; usun[k] = {{klocki.find({x + 1, y}) == klocki.end(), klocki.find({x - 1, y}) == klocki.end()}, {klocki.find({x, y + 1}) == klocki.end(), klocki.find({x, y - 1}) == klocki.end()}}; if (usun[k].first == make_pair(true, true) || usun[k].second == make_pair(true, true)) { q.push(k); // cerr << "wrzucam " << k.first << " " << k.second << "\n"; } } } int bfs(queue<pair<int, int>>& q) { int ile = 0; while (!q.empty()) { // { pair<int, int> k = q.front(); // cerr << "przetwarzam " << k.first << " " << k.second << "\n"; int x = k.first, y = k.second; q.pop(); ile++; if (klocki.find({x - 1, y}) != klocki.end()) { usun[{x - 1, y}].first.first = 1; if (usun[{x - 1, y}].first == make_pair(true, true) && usun[{x - 1, y}].second != make_pair(true, true)) { q.push({x - 1, y}); // cerr << "wrzucam " << x - 1 << " " << y << "\n"; } } if (klocki.find({x + 1, y}) != klocki.end()) { usun[{x + 1, y}].first.second = 1; if (usun[{x + 1, y}].first == make_pair(true, true) && usun[{x + 1, y}].second != make_pair(true, true)) { q.push({x + 1, y}); // cerr << "wrzucam " << x + 1 << " " << y << "\n"; } } if (klocki.find({x, y - 1}) != klocki.end()) { usun[{x, y - 1}].second.first = 1; if (usun[{x, y - 1}].second == make_pair(true, true) && usun[{x, y - 1}].first != make_pair(true, true)) { q.push({x, y - 1}); // cerr << "wrzucam " << x << " " << y - 1 << "\n"; } } if (klocki.find({x, y + 1}) != klocki.end()) { usun[{x, y + 1}].second.second = 1; if (usun[{x, y + 1}].second == make_pair(true, true) && usun[{x, y + 1}].first != make_pair(true, true)) { q.push({x, y + 1}); // cerr << "wrzucam " << x << " " << y + 1 << "\n"; } } } return ile; } int check() { queue<pair<int, int>> q; fill(q); return bfs(q); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k, q; cin >> n >> m >> k >> q; for (int i = 0; i < k; i++) { int x, y; cin >> x >> y; klocki.insert({x, y}); } int out = check(); cout << out << "\n"; for (int i = 0; i < q; i++) { int x, y; cin >> x >> y; auto it = klocki.find({x, y}); if (it != klocki.end()) { klocki.erase(it); // jeśli usuwam coś, co i tak byłoby usunięte if (usun[{x, y}].first == make_pair(true, true) || usun[{x, y}].second == make_pair(true, true)) { out--; } else { queue<pair<int, int>> queue; queue.push({x, y}); out += bfs(queue) - 1; } } else { klocki.insert({x, y}); usun[{x, y}] = {{klocki.find({x + 1, y}) == klocki.end(), klocki.find({x - 1, y}) == klocki.end()}, {klocki.find({x, y + 1}) == klocki.end(), klocki.find({x, y - 1}) == klocki.end()}}; if (usun[{x, y}].first == make_pair(true, true) || usun[{x, y}].second == make_pair(true, true)) { out++; } else { out = check(); } } cout << out << "\n"; } } |