【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;
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 {
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()```