P10864 [HBCPC2024] Genshin Impact Startup Forbidden II题目描述弹窗内容LeavingZ你被禁止玩《原神》。蓝边铅球因LeavingZ的禁止而无法玩《原神》所以她转向了围棋。围棋游戏由两名玩家进行一方使用黑子另一方使用白子。两名玩家轮流下子黑子先行。围棋棋盘由19 × 19 19\times 1919×19的交叉点组成我们用( x , y ) (x,y)(x,y)表示第x xx行第y yy列的交叉点。棋子放置在交叉点上。左上角为( 1 , 1 ) (1,1)(1,1)右下角为( 19 , 19 ) (19,19)(19,19)。如果∣ x 1 − x 2 ∣ ∣ y 1 − y 2 ∣ 1 |x_1-x_2| |y_1-y_2| 1∣x1​−x2​∣∣y1​−y2​∣1那么交叉点( x 1 , y 1 ) (x_1,y_1)(x1​,y1​)和( x 2 , y 2 ) (x_2,y_2)(x2​,y2​)是相邻的。相邻的交叉点上放置相同颜色的棋子属于同一组棋子。一个棋子的“气”数等于该棋子所在交叉点的相邻交叉点上没有棋子的个数。一组棋子的“气”数等于该组棋子中所有棋子的“气”数之和。一组棋子如果“气”数为零则被视为“死棋”并且必须从棋盘上移除。注意在黑子落子后优先移除任何死掉的白子然后重新计算黑子的“气”数。这是因为可能出现这样的情况黑子落子后黑白两方的棋子都没有“气”但移除死掉的白子会增加黑子的“气”。白子落子的处理方式类似。在白子落子后优先移除任何死掉的黑子然后重新计算白子的“气”数。现在有一局围棋从空棋盘开始总共进行了m mm步。给定每步棋子的放置位置请输出每步棋子落子后分别有多少颗黑子和白子被移除。显然黑子在奇数步落子白子在偶数步落子。保证棋子放置在空的交叉点上。注意棋子可以放置在任意 \textbf{任意}任意当前没有棋子的交叉点上无论是否违反了现实中的围棋规则( 1 ) ^{(1)}(1)。注释(2):译者补充输入格式输入包含m mm行1 ≤ m ≤ 5 × 10 5 1 \le m \le 5\times 10^51≤m≤5×105第i ii行包含两个整数x i , y i x_i, y_ixi​,yi​1 ≤ x i , y i ≤ 19 1 \le x_i, y_i \le 191≤xi​,yi​≤19表示第i ii步在( x i , y i ) (x_i, y_i)(xi​,yi​)位置放置棋子。保证棋子放置在当前没有棋子的交叉点上。输出格式输出包含m mm行每行包含两个整数。第i ii行的第一个整数表示第i ii步后被移除的黑子数量第二个整数表示被移除的白子数量。翻译者Immunoglobules输入输出样例 #1输入 #18 2 1 1 1 1 2 2 2 1 1 1 3 2 3 3 1输出 #10 0 0 0 0 1 0 0 0 0 0 0 0 0 3 0C实现#includebits/stdc.husingnamespacestd;#definellint#definefifirst#definesesecondintm,x,y,black,white,qi[20][20];intdx[]{-1,0,0,1},dy[]{0,-1,1,0};queuepairll,llq;vectorpairll,lle;boolvis[20][20];boolok(ll x,ll y){return1xx191yy19;}voidbfs(ll x,ll y,boolcol){q.push({x,y});e.clear();boolflag0;while(!q.empty()){//检查这块棋是否有气autotmpq.front();q.pop();ll xxtmp.fi,yytmp.se;if(!flag)e.push_back({xx,yy});for(intk0;k4;k){ll pxxxdx[k],pyyydy[k];if(!ok(px,py)||qi[px][py]!col)continue;if(qi[px][py]-1){flag1;continue;}//记得写 continue!if(vis[px][py])continue;vis[px][py]1,q.push({px,py});}}if(flag)return;if(col)blacke.size();elsewhitee.size();for(autopp:e)qi[pp.fi][pp.se]-1;}voidsolve(boolcol){blackwhite0;for(inti1;i19;i)for(intj1;j19;j)vis[i][j]0;for(inti1;i19;i)for(intj1;j19;j)if(!vis[i][j]qi[i][j]!col)vis[i][j]1,bfs(i,j,!col);//先删对方的再删自己的for(inti1;i19;i)for(intj1;j19;j)if(!vis[i][j]qi[i][j]col)vis[i][j]1,bfs(i,j,col);coutblack white\n;}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);for(inti1;i19;i)for(intj1;j19;j)qi[i][j]-1;cinm;for(inti1;im;i)cinxy,qi[x][y](i1),solve(i1);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容