hdu 4775 Infinite Go(暴力)-白红宇

hdu 4775 Infinite Go(暴力)

阅读量：5933 次

发布时间：2019-06-19

本文共 3008 字，大约阅读时间需要 10 分钟。

题目大意：两个人下围棋，总共走了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 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           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
           
             pii;int N, Nw, Nb, X[maxn+5], Y[maxn+5], f[maxn+5], c[maxn+5];map
            
              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
             
               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;}

转载地址：http://fyjtx.baihongyu.com/

你可能感兴趣的文章