【HDOJ】4775 Infinite Go
其实是一道模拟题，并查集用来优化。还可以的一道题目。
1 /* 4775 */
2 #include <iostream>
3 #include <sstream>
4 #include <string>
5 #include <map>
6 #include <queue>
7 #include <set>
8 #include <stack>
9 #include <vector>
10 #include <deque>
11 #include <algorithm>
12 #include <cstdio>
13 #include <cmath>
14 #include <ctime>
15 #include <cstring>
16 #include <climits>
17 #include <cctype>
18 #include <cassert>
19 #include <functional>
20 #include <iterator>
21 #include <iomanip>
22 using namespace std;
23 //#pragma comment(linker,"/STACK:102400000,1024000")
24
25 #define sti set<int>
26 #define stpii set<pair<int, int> >
27 #define mpii map<int,int>
28 #define vi vector<int>
29 #define pii pair<int,int>
30 #define vpii vector<pair<int,int> >
31 #define rep(i, a, n) for (int i=a;i<n;++i)
32 #define per(i, a, n) for (int i=n-1;i>=a;--i)
33 #define clr clear
34 #define pb push_back
35 #define mp make_pair
36 #define fir first
37 #define sec second
38 #define all(x) (x).begin(),(x).end()
39 #define SZ(x) ((int)(x).size())
40 #define lson l, mid, rt<<1
41 #define rson mid+1, r, rt<<1|1
42
43 const int maxn = 10005;
44 map<pii, int> id;
45 map<pii, bool> visit;
46 map<pii, int>::iterator iter;
47 int X[maxn], Y[maxn];
48 int sz[maxn], fa[maxn];
49 int dir[4][2] = {
50 -1,0, 1,0, 0,-1, 0,1
51 };
52 int n;
53
54 int find(int x) {
55 if (x == fa[x])
56 return x;
57
58 return fa[x] = find(fa[x]);
59 }
60
61 bool judge(int x, int y) {
62 return x<=0 || y<=0;
63 }
64
65 void remove(int bx, int by, int uid) {
66 queue<pii> Q;
67 int x, y;
68 pii p(bx, by), pp;
69
70 visit.clr();
71 Q.push(p);
72 visit[p] = true;
73
74 while (!Q.empty()) {
75 p = Q.front();
76 Q.pop();
77
78 // remove from the id
79 iter = id.find(p);
80 fa[iter->sec] = iter->sec;
81 sz[iter->sec] = 0;
82 id.erase(iter);
83
84 rep(j, 0, 4) {
85 x = p.fir + dir[j][0];
86 y = p.sec + dir[j][1];
87 if (judge(x, y))
88 continue;
89
90 pp.fir = x;
91 pp.sec = y;
92 if (visit[pp])
93 continue;
94
95 iter = id.find(pp);
96 if (iter == id.end())
97 continue;
98
99 if ((iter->sec&1) ^ uid) {
100 int f = find(iter->sec);
101 ++sz[f];
102 } else {
103 visit[pp] = true;
104 Q.push(pp);
105 }
106 }
107 }
108 }
109
110 void solve() {
111 rep(i, 0, n+1)
112 fa[i] = i;
113 memset(sz, 0, sizeof(sz));
114 id.clr();
115
116 int vac, x, y;
117 int xx, yy;
118 pii p;
119
120 rep(i, 1, n+1) {
121 p.fir = x = X[i];
122 p.sec = y = Y[i];
123 id[p] = i;
124 vac = 0;
125 rep(j, 0, 4) {
126 xx = x + dir[j][0];
127 yy = y + dir[j][1];
128 if (judge(xx, yy))
129 continue;
130
131 iter = id.find(mp(xx, yy));
132 if (iter == id.end()) {
133 ++vac;
134 } else {
135 int f = find(iter->sec);
136 --sz[f];
137 }
138 }
139 sz[i] = vac;
140 rep(j, 0, 4) {
141 xx = x + dir[j][0];
142 yy = y + dir[j][1];
143 if (judge(xx, yy))
144 continue;
145
146 iter = id.find(mp(xx, yy));
147 if (iter == id.end())
148 continue;
149
150 if ((iter->sec & 1) ^ (i & 1)) {
151 // delete enemy
152 int fx = find(iter->sec);
153 if (sz[fx] == 0) {
154 remove(xx, yy, iter->sec&1);
155 }
156
157 } else {
158 // link self
159 int fx = find(iter->sec);
160 int fy = find(i);
161 if (fx != fy) {
162 fa[fx] = fy;
163 sz[fy] += sz[fx];
164 }
165 }
166 }
167
168 int f = find(i);
169 if (sz[f] == 0) {
170 remove(x, y, i&1);
171 }
172 }
173
174 int ansa, ansb;
175
176 ansa = ansb = 0;
177 visit.clr();
178 per(i, 1, n+1) {
179 p.fir = X[i];
180 p.sec = Y[i];
181 iter = id.find(p);
182 if (iter==id.end() || visit[p])
183 continue;
184
185 visit[p] = true;
186 if (iter->sec & 1)
187 ++ansa;
188 else
189 ++ansb;
190 }
191
192 printf("%d %d\n", ansa, ansb);
193 }
194
195 int main() {
196 ios::sync_with_stdio(false);
197 #ifndef ONLINE_JUDGE
198 freopen("data.in", "r", stdin);
199 freopen("data.out", "w", stdout);
200 #endif
201
202 int t;
203
204 scanf("%d", &t);
205 while (t--) {
206 scanf("%d", &n);
207 rep(i, 1, n+1)
208 scanf("%d %d", &X[i], &Y[i]);
209 solve();
210 }
211
212 #ifndef ONLINE_JUDGE
213 printf("time = %d.\n", (int)clock());
214 #endif
215
216 return 0;
217 }数据发生器。
1 from random import randint, shuffle
2 import shutil
3 import string
4
5
6 def GenDataIn():
7 with open("data.in", "w") as fout:
8 t = 10
9 fout.write("%d\n" % t)
10 bound = 10**2
11 for tt in xrange(t):
12 n = randint(1000, 5000)
13 fout.write("%d\n" % n)
14 d = dict()
15 for i in xrange(n):
16 while True:
17 x = randint(1, bound)
18 y = randint(1, bound)
19 tpl = (x, y)
20 if tpl not in d:
21 d[tpl] = True
22 break
23 fout.write("%d %d\n" % (x, y))
24
25
26 def MovDataIn():
27 desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"
28 shutil.copyfile("data.in", desFileName)
29
30
31 if __name__ == "__main__":
32 GenDataIn()
33 MovDataIn()