7_11_ F题 Infinite Go(并查集)

baidu_19306071 · · 739 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

7_11_ F题 Infinite Go(并查集)


简单题意

按围棋规则落子,给出每次落子的坐标,问最后棋盘上剩余的黑白子的数量

思路

用并查集来维护棋盘上的的联通块的气,然后就按照围棋规则去模拟就好了,注意提子之后要把对应的位置还原成可用状态,可有气,可落子,这题细节较多,要注意。

代码

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e4+10;
int mov[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int fa[maxn];
set<pair<int, int> > space[maxn];
map<pair<int ,int>,int>M ,idx;

void init(int n){
    for(int i = 0 ; i <= n ; i ++){
        fa[i] = i;
        space[i].clear();
    }
    M.clear();
    idx.clear();
}

int Find (int x){
   return fa[x] == x ? x:fa[x] = Find(fa[x]);
}

void Union(int x,int y){
    x = Find(x);
    y = Find(y);
    if(space[x].size() < space[y].size()) swap(x,y);
    fa[y] = x;
    for(auto it = space[y].begin() ; it != space[y].end() ; it ++)
        space[x].insert(*it);
    space[y].clear();
}

inline int getColor(int x,int y){
    if(M.find(make_pair(x,y)) == M.end()) return -1;
    return M[make_pair(x,y)];
}

void del(pair<int,int> start ,int col){
    queue<pair<int,int> > que;
    que.push(start);
    while(!que.empty()){
        auto cur=que.front();
        que.pop();
        M.erase(cur);
        for(int i = 0;i < 4;i++){
            int x = cur.first + mov[i][0];
            int y = cur.second + mov[i][1];
            if(x <= 0 || y <= 0) continue;

            auto next = make_pair(x,y);
            if(getColor(x,y) == col )
                que.push(next);
            else if(getColor(x,y) == (col^1))
                space[Find(idx[next])].insert(cur);
        }
    }
}

void put(int x,int y,int col){
    auto cur = make_pair(x,y);
    M[cur] = col;
    for(int i = 0; i < 4; i++){
        x = cur.first + mov[i][0];
        y = cur.second+ mov[i][1];
        if(x <= 0 || y <= 0) continue;

        auto next = make_pair(x,y);

        if(getColor(x,y) == col)
            Union(idx[cur],idx[next]);
        else if(getColor(x,y) == -1)
            space[Find(idx[cur])].insert(next);
        else{
            space[Find(idx[next])].erase(cur);
            if(space[Find(idx[next])].size() == 0)
                del(next,col^1);
        }
    }
    space[Find(idx[cur])].erase(cur);
    if(space[Find(idx[cur])].size()==0)
        del(cur,col);
}

int main(){
    int T,n;
    scanf("%d", &T);
    while(T --){
        scanf("%d",&n);
        init(n);
        int col = 0;
        for(int i = 0 ; i < n ; i ++,col ^= 1){
            int x,y;
            scanf("%d %d",&x,&y);
            idx[make_pair(x,y)] = i+1;
            put(x,y,col);
        }
        int black = 0,white = 0;
        for(auto it = M.begin(); it != M.end(); it ++){
            if(it->second == 0) black ++;
            else white ++;
        }
        printf("%d %d\n",black,white);
    }
    return 0;
}

有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:baidu_19306071

查看原文:7_11_ F题 Infinite Go(并查集)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

739 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传