#include <bits/stdc++.h> using namespace std; int n, m, k, q; int x, y; unordered_set<long long> tiles; int ans; long long id(int tile_x, int tile_y) { return ((long long)tile_x - 1) * m + tile_y + 1; } bool is(long long tile_id) { return tiles.find(tile_id) != tiles.end(); } bool can_remove(long long tile_id) { return (!is(tile_id - m) && !is(tile_id + m)) || (!is(tile_id - 1) && !is(tile_id + 1)); } int solve() { unordered_set<long long> tiles_cpy = tiles; queue<long long> Q; for(long long tile_id : tiles_cpy) { if(can_remove(tile_id)) { Q.push(tile_id); tiles.erase(tile_id); } } while(!Q.empty()) { long long tile_id = Q.front(); Q.pop(); for(long long next_tile_id : {tile_id - m, tile_id + 1, tile_id + m, tile_id - 1}) { if(is(next_tile_id) && can_remove(next_tile_id)) { Q.push(next_tile_id); tiles.erase(next_tile_id); } } } swap(tiles, tiles_cpy); return tiles.size() - tiles_cpy.size(); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m >> k >> q; m += 2; for(int i = 1; i <= k; i++) { cin >> x >> y; tiles.insert(id(x, y)); } ans = solve(); cout << ans; for(int i = 1; i <= q; i++) { cin >> x >> y; long long tile_id = id(x, y); int adj = 0; for(long long next_tile_id : {tile_id - m, tile_id + 1, tile_id + m, tile_id - 1}) { if(is(next_tile_id)) { adj++; } } if(is(tile_id)) { tiles.erase(tile_id); if(adj <= 1) { ans--; } } else { tiles.insert(tile_id); if(adj <= 1) { ans++; } } if(adj > 1) { ans = solve(); } cout << '\n' << ans; } }
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 | #include <bits/stdc++.h> using namespace std; int n, m, k, q; int x, y; unordered_set<long long> tiles; int ans; long long id(int tile_x, int tile_y) { return ((long long)tile_x - 1) * m + tile_y + 1; } bool is(long long tile_id) { return tiles.find(tile_id) != tiles.end(); } bool can_remove(long long tile_id) { return (!is(tile_id - m) && !is(tile_id + m)) || (!is(tile_id - 1) && !is(tile_id + 1)); } int solve() { unordered_set<long long> tiles_cpy = tiles; queue<long long> Q; for(long long tile_id : tiles_cpy) { if(can_remove(tile_id)) { Q.push(tile_id); tiles.erase(tile_id); } } while(!Q.empty()) { long long tile_id = Q.front(); Q.pop(); for(long long next_tile_id : {tile_id - m, tile_id + 1, tile_id + m, tile_id - 1}) { if(is(next_tile_id) && can_remove(next_tile_id)) { Q.push(next_tile_id); tiles.erase(next_tile_id); } } } swap(tiles, tiles_cpy); return tiles.size() - tiles_cpy.size(); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m >> k >> q; m += 2; for(int i = 1; i <= k; i++) { cin >> x >> y; tiles.insert(id(x, y)); } ans = solve(); cout << ans; for(int i = 1; i <= q; i++) { cin >> x >> y; long long tile_id = id(x, y); int adj = 0; for(long long next_tile_id : {tile_id - m, tile_id + 1, tile_id + m, tile_id - 1}) { if(is(next_tile_id)) { adj++; } } if(is(tile_id)) { tiles.erase(tile_id); if(adj <= 1) { ans--; } } else { tiles.insert(tile_id); if(adj <= 1) { ans++; } } if(adj > 1) { ans = solve(); } cout << '\n' << ans; } } |