题目链接：hdu 4775 Infinite Go
题目大意：两个人下围棋，总共走了n步。黑棋和白棋交替走，假设一片棋的上下左右被封死，那么该片棋子就会被吃掉，问说最后黑白棋各剩多少个。
解题思路：比較恶心的模拟题，相邻同样色的棋子要用并查集连接。而且要记录每片棋子还剩的空格数。假设空格数为0的话说明该片棋子被其它颜色围住，则要剔除掉，不且将相邻的位置不同色的棋空格数加1。主要是细节上的问题。
例子 8 7 5 5 4 5 3 5 3 4 4 4 3 3 4 6 18 1 3 1 4 2 2 1 5 2 4 2 3 3 1 3 2 3 5 3 4 4 2 4 3 4 4 1 6 5 3 3 3 1 10 3 3 12 1 2 1 1 2 1 2 2 1 3 3 1 2 3 1 4 3 2 3 3 4 2 2 4 4 1 1 1 2 2 2 2 1 4 2000000000 2000000000 2000000000 1999999999 1999999999 1999999999 1999999999 2000000000 8 1 2 4 1 2 1 4 2 2 3 4 3 3 2 2 2 17 1 3 1 4 2 2 1 5 2 4 2 3 3 1 3 2 3 5 3 4 4 2 4 3 4 4 1 6 5 3 30 30 3 3 17 1 3 1 4 2 2 1 5 2 4 2 3 3 1 3 2 3 5 3 4 4 2 3 3 4 4 1 6 5 3 4 3 100 100 答案 4 2 9 4 6 4 1 2 2 2 4 3 9 4 9 3
#include <cstdio> #include <cstring> #include <vector> #include <map> #include <queue> #include <algorithm> using namespace std; const int maxn = 1e4; const int INF = 2*1e9+10; const int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; typedef pair<int, int> pii; int N, Nw, Nb, X[maxn+5], Y[maxn+5], f[maxn+5], c[maxn+5]; map<pii, int> R; void init () { scanf("%d", &N); Nw = N / 2; Nb = N - Nw; R.clear(); for (int i = 0; i < N; i++) { f[i] = i; c[i] = 0; } } inline int bit (int x) { return x&1; } int getfar (int x) { return f[x] == x ? x : f[x] = getfar(f[x]); } inline bool isEmpty (int x, int y) { if (x <= 0 || y <= 0 || x >= INF || y >= INF) return false; if (R.count(make_pair(x, y))) return false; return true; } inline int count_empty (pii u) { int cnt = 0; for (int i = 0; i < 4; i++) { int x = u.first + dir[i][0]; int y = u.second + dir[i][1]; if (isEmpty(x, y)) cnt++; } return cnt; } inline void link_board (int x, int y) { int fx = getfar(x); int fy = getfar(y); f[fy] = fx; c[fx] += c[fy]; /**/ c[fx]--; } int del_board (int col, int x, int y) { int cnt = 1; pii u = make_pair(x, y); queue<pii> que; que.push(u); f[R[u]] = R[u]; R.erase(u); while (!que.empty()) { u = que.front(); que.pop(); for (int i = 0; i < 4; i++) { int p = u.first + dir[i][0]; int q = u.second + dir[i][1]; if (p <= 0 || p >= INF || q <= 0 || q >= INF) continue; pii v = make_pair(p, q); if (!R.count(v)) continue; int set = R[v]; if (bit(set) != col) { int k = getfar(set); c[k]++; continue; } f[R[v]] = R[v]; R.erase(v); cnt++; que.push(v); } } return cnt; } void del_empty (int k) { int fk = getfar(k); c[fk]--; if (c[fk] == 0) { int set = bit(fk); int cnt = del_board(set, X[fk], Y[fk]); if (set) Nw -= cnt; else Nb -= cnt; } } void solve () { for (int i = 0; i < N; i++) { scanf("%d%d", &X[i], &Y[i]); pii v = make_pair(X[i], Y[i]); c[i] = count_empty(v); R[v] = i; for (int j = 0; j < 4; j++) { int p = X[i] + dir[j][0]; int q = Y[i] + dir[j][1]; if (p <= 0 || q <= 0 || p >= INF || q >= INF) continue; pii u = make_pair(p, q); if (!R.count(u)) continue; int k = R[u]; if (bit(i) == bit(k)) link_board(i, k); else del_empty(k); } int fi = getfar(i); if (c[fi] == 0) { int cnt = del_board(bit(fi), X[fi], Y[fi]); if (bit(fi)) Nw -= cnt; else Nb -= cnt; } } printf("%d %d\n", Nb, Nw); } int main () { int cas; scanf("%d", &cas); while (cas--) { init(); solve(); } return 0; }转载于:https://www.cnblogs.com/bhlsheji/p/5283020.html
相关资源：数据结构—成绩单生成器