题解：P10864 [HBCPC2024] Genshin Impact Startup Forbidden II

【题目大意】

模拟围棋的落子过程，然后根据围棋的气来计算每一步落子后被提子的个数。

当然强调了，每一步的落子没有限制，也就有可能某个棋子刚落下去后会直接被提掉。

【思路】

直接在落子后暴力搜索计算出相邻的棋子所在块的气，最后在计算落子位置所在块的气。

具体来说，对于从 $(x,y)$ 开始搜索的棋子，每到达一个未被访问到的同色棋子的块，就加入到集合中；每到达一个未被访问到的空位，就把该连通块的气的数目加一。

由于时限为 $4s$，并且棋盘的大小是 $19 \times 19$ 的，所以复杂度为 $O(m)$，可以通过此题。

【代码】

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define init(x) memset (x,-1,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
vector <pair <int,int> > v;
int t,outa,outb,cnt;
int a[25][25],vis[25][25],sx[] = {0,0,1,-1},sy[] = {1,-1,0,0}; 
void search (int x,int y,int col);
int main ()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    t = read ();init (a);
    for (int i = 1;i <= t;++i)
    {
        int x = read (),y = read (),ty = (i & 1) ? 0 : 1;//ty = 1 为白棋
        a[x][y] = ty;outa = outb = 0;
//先处理对手的气的情况，提完子后再处理自己的气
        for (int i = 0;i < 4;++i)//处理这个棋子的相邻位置
        {
            int xx = x + sx[i],yy = y + sy[i];
            cnt = 0;v.clear ();
            if (1 <= xx && xx <= 19 && 1 <= yy && yy <= 19)
            {
                if (a[xx][yy] == (ty ^ 1) && !vis[xx][yy]) search (xx,yy,ty ^ 1);
                if (!cnt)//没有气会被提子
                {
                    if (ty == 0) outb += v.size ();
                    else outa += v.size ();//提子的数目即为 v 的大小
                    for (auto p : v) a[p.first][p.second] = -1;//清空这些位置
                }
            }
        }
        cnt = 0;v.clear ();
        search (x,y,ty);
        if (!cnt)
        {
            if (ty == 0) outa += v.size ();
            else outb += v.size ();
            for (auto p : v) a[p.first][p.second] = -1;
        }
        for (int i = 1;i <= 19;++i)
            for (int j = 1;j <= 19;++j) vis[i][j] = 0;
        printf ("%d %d\n",outa,outb);
    }
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}
void search (int x,int y,int col)
{
    vis[x][y] = 1;v.push_back ({x,y});//标记
    for (int i = 0;i < 4;++i)
    {
        int xx = x + sx[i],yy = y + sy[i];
        if (1 <= xx && xx <= 19 && 1 <= yy && yy <= 19)
        {
            if (a[xx][yy] == -1) ++cnt;//空位
            if (a[xx][yy] == col && !vis[xx][yy]) search (xx,yy,col);
        }
    }
}