P10864 [HBCPC2024] Genshin Impact Startup Forbidden II 题解

· · 题解

题意简述

在一局围棋中，给你黑方与白方每一步的落子，问你每一步黑白双方有几个子被吃？

Sol

很简单啊，我们可以每一步落子之后，对这个棋子周围的五个位置（包括自己的位置）的联通块处理即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
int board[30][30],ans[10],n=19;
bool used[30][30];
void bfs(int x,int y){
    int col=board[x][y];
    queue<pair<int,int>> que;
    vector<pair<int,int>> v;
    que.push(make_pair(x,y));
    used[x][y]=true;
    bool ok=false;
    while(!que.empty()){
        auto [x,y]=que.front();
        que.pop();
        v.push_back(make_pair(x,y));
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>n)
                continue;
            if(board[nx][ny]==-1)
                ok=true;
            if(board[nx][ny]!=col || used[nx][ny])
                continue;
            que.push(make_pair(nx,ny));
            used[nx][ny]=true;
        }
    }
    if(!ok){
        for(auto &[x,y]:v){
            board[x][y]=-1;
            ans[col]++;
        }
    }
    return;
}
void solve(int col,vector<pair<int,int>> &v){
    memset(used,0,sizeof(used));
    for(auto &[x,y]:v){
        if(x<1 || x>n || y<1 || y>n)
            continue;
        if(used[x][y])
            continue;
        if(board[x][y]!=col)
            continue;
        bfs(x,y);
    }
    for(auto &[x,y]:v){
        if(x<1 || x>n || y<1 || y>n)
            continue;
        if(used[x][y])
            continue;
        if(board[x][y]!=1^col)
            continue;
        bfs(x,y);
    }
    return;
}
int main(){
    memset(board,-1,sizeof(board));
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        int col=i%2;
        board[x][y]=col;
        ans[1]=ans[0]=0;
        vector<pair<int,int>> v;
        for(int i=0;i<4;i++)
            v.push_back(make_pair(x+dx[i],y+dy[i]));
        v.push_back(make_pair(x,y));
        solve(col^1,v);
        cout<<ans[1]<<' '<<ans[0]<<endl;
    }
    return 0;
}