本文共 2670 字，大约阅读时间需要 8 分钟。
为了解决这个问题，我们需要确保在改造设备塔的区块时，不会断开数据通道，使得设备塔的两端无法连通。我们可以使用并查集（Union-Find）数据结构来高效地管理各个区块的连通性。
#includeint n, m, k;int fx[8] = { -2*m-1, -2*m, -2*m+1, -1, 1, 2*m-1, 2*m, 2*m+1 };int B[200001] = {0};int f[200001];int find(int d) { if (f[d] == 0 || f[d] == d) return d; return f[d] = find(f[d]);}int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= k; ++i) { int a, b; scanf("%d%d", &a, &b); int l1bh = (a-1) * 2 * m + b; int l2bh = l1bh + m; int pd = 0; for (int ii = 0; ii < 8 && pd == 0; ++ii) { int bh1 = l1bh + fx[ii]; if ((l1bh - 1) % (2 * m) == 0) { if (ii == 0) bh1 = l1bh - 1; if (ii == 3) bh1 = l1bh + 2 * m - 1; if (ii == 5) bh1 = l1bh + 4 * m - 1; } if (bh1 > 0 && bh1 <= 2 * n * m) { if (B[bh1] == 1) { for (int j = 0; j < 8; ++j) { int bh2 = l2bh + fx[j]; if (l2bh % (2 * m) == 0) { if (j == 2) bh2 = l2bh - 4 * m + 1; if (j == 4) bh2 = l2bh - 2 * m + 1; if (j == 7) bh2 = l2bh + 1; } if (bh2 > 0 && bh2 <= 2 * n * m) { if (B[bh2] == 1) { if (find(bh1) == find(bh2)) { pd = 1; break; } } } } } } } if (pd == 0) { ++Ans; B[l1bh] = B[l2bh] = 1; for (int j = 0; j < 8; ++j) { int bh1 = l1bh + fx[j]; if ((l1bh - 1) % (2 * m) == 0) { if (j == 0) bh1 = l1bh - 1; if (j == 3) bh1 = l1bh + 2 * m - 1; if (j == 5) bh1 = l1bh + 4 * m - 1; } if (bh1 > 0 && bh1 <= 2 * n * m) { if (B[bh1] == 1) { int root1 = find(l1bh); int root2 = find(bh1); f[root1] = root2; } } } } } printf("%d", Ans);}
f来记录每个节点的父节点，初始时每个节点的父节点为0。转载地址：http://qqkg.baihongyu.com/