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;
}

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

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传