自动搬运

查看原文

来自洛谷，原作者为

	jianhe 以颤抖之身追赶，怀敬畏之心挑战。--《棋魂》|| 最后在线时间：2025年8月23日22时4分

搬运于2025-08-24 23:01:59，当前版本为作者最后更新于2024-08-19 11:06:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

两个人下围棋，保证每次下在空位上，求每步棋后，被吃掉的黑子与白子数量。

思路：

众所周知，围棋棋盘大小是 $19 \times 19$ 的，因此我们可以采取比较暴力的方式：在每步棋后，暴力搜索整个棋盘，寻找没有气的棋子，并统计答案。

为保证复杂度，我们用 $vis$ 数组标记一个位置是否被遍历过。

有许多要注意的细节：

1. 要先提对方的棋子，再提自己的。
2. $vis$ 数组每次都要清空。
3. 不要忘记写 continue。
4. 可以用 -1 表示没有棋子。
5. 记得删除被吃掉的棋子（标记为 $-1$）。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define fi first
#define se second
ll m,x,y,black,white,qi[20][20];
ll dx[]={-1,0,0,1};
ll dy[]={0,-1,1,0};
queue<pair<ll,ll> > q;
vector<pair<ll,ll> > e;
bool vis[20][20];
bool ok(ll x,ll y){return 1<=x&&x<=19&&1<=y&&y<=19;}
void bfs(ll x,ll y,bool col){
	q.push({x,y});e.clear();
	bool flag=0;
	while(!q.empty()){//检查这块棋是否有气
		auto tmp=q.front();q.pop();
		ll xx=tmp.fi,yy=tmp.se;
		if(!flag) e.push_back({xx,yy});
		for(int k=0;k<4;k++){
			ll px=xx+dx[k],py=yy+dy[k];
			if(!ok(px,py)||qi[px][py]==!col) continue;
			if(qi[px][py]==-1){flag=1;continue;}//记得写 continue!
			if(vis[px][py]) continue;
			vis[px][py]=1,q.push({px,py});
		}
	}
	if(flag) return;
	if(col) black+=e.size();
	else white+=e.size();
	for(auto pp:e) qi[pp.fi][pp.se]=-1;
}
void solve(bool col){
	black=white=0;
	for(int i=1;i<=19;i++)
		for(int j=1;j<=19;j++) vis[i][j]=0;
	for(int i=1;i<=19;i++)
		for(int j=1;j<=19;j++)
			if(!vis[i][j]&&qi[i][j]==!col) vis[i][j]=1,bfs(i,j,!col);//先删对方的，再删自己的
	for(int i=1;i<=19;i++)
		for(int j=1;j<=19;j++)
			if(!vis[i][j]&&qi[i][j]==col) vis[i][j]=1,bfs(i,j,col);
	cout<<black<<" "<<white<<"\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	for(int i=1;i<=19;i++)
		for(int j=1;j<=19;j++) qi[i][j]=-1;
    //-1 表示没有棋，1 表示黑棋，0 表示白棋
	cin>>m;
	for(int i=1;i<=m;i++)
		cin>>x>>y,qi[x][y]=(i&1),solve(i&1);
	return 0;
}