P10864 [HBCPC2024] Genshin Impact Startup Forbidden II 题解

jianhe · 2024-08-19 11:06:27 · 题解

题意：

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

思路：

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

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

有许多要注意的细节：

1. 要先提对方的棋子，再提自己的。
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;
}