题解：P16403 [ECUSTPC 2026 Spring] 净化行动 2

· · 题解

题意简述

无限棋盘上有一个黑将和若干固定的黑卒。红炮可以部署在任意空位，并按中国象棋的炮规则移动或吃子。判断是否存在吃掉黑将的方案。

解题思路

把每枚黑棋视为一条边，连接它所在的横线与纵线。由黑将对应的边出发，在这个行列二分图中取连通块。记块内棋子集合为 S。其他棋子不与 S 中任何棋子同行或同列。它们不会成为攻击块内棋子的炮架或障碍，所以后续只需考虑 S。

称一条包含 S 中棋子的行或列为稳定线。稳定线上只有 1 枚棋子，或恰有 3 枚连续棋子。三连的中间棋子称为该线的中点。

答案为 NO 的充要条件如下：

这组条件可以局部检查，无需还原整个特殊图形。实现时，先按横坐标和纵坐标分别保存棋子编号。从黑将开始广度优先搜索；每次取出一枚棋子，就加入同一行与同一列的所有棋子。每个坐标组处理后立即清空，因此搜索总共只遍历 O(n) 个编号。

得到 S 后，重新按行、列分组并排序。一组坐标必须是单点，或形如 z,z+1,z+2。若是三连，则取中间坐标，到垂直分组中检查对应棋子是否也是中点。把行列互换后再检查一次，即可覆盖两个方向，同时记录黑将是否位于中点。

使用有序映射分组和排序，总时间复杂度为 O(n\log n)，空间复杂度为 O(n)。

正确性证明

先说明为何可以删去 S 外的棋子。任何经过 S 中棋子的行或列，其上若还有黑棋，该棋子也会进入同一连通块。因此，S 外棋子不会出现在涉及 S 的直线上。外部操作至多把炮送到另一个空位，而炮本来就能部署在任意空位。故删去 S 外棋子不会改变能否吃掉黑将。

接着考虑一条非稳定线。把线上棋子从一侧依次编号。

所以，非稳定线上的任意指定棋子都能被吃掉，且炮能回到与无穷远连通的空位。

行列二分图中的 S 是连通的。若存在非稳定线，取它到黑将所在行或列的一条简单路径。先在当前非稳定线上吃掉它与下一条线交点处的棋子。路径中的下一条内部线至少包含前后两个交点；若它原来稳定，就只能是三连，删去一个交点后变成非稳定线。依此传播，最终黑将所在的线会变得可操作，并能吃掉黑将。因此，答案为 NO 时，所有占用线都必须稳定。

现在假设所有占用线都稳定。取某条三连的中点，从该线外侧用端点作炮架，可以直接吃掉中点。若垂直方向不是以它为中点的三连，则垂直线只能是单点，或该棋子是三连的端点。吃子后，炮都能沿垂直方向离开。原三连随即只剩两枚棋子，便可按上一段传播到黑将。因此，答案为 NO 时，每个三连中点必须同时是垂直三连中点。

最后证明这两个结构条件也足以限制红炮。若一个空位的某条水平或垂直直线两侧都有黑棋，该线就不是稳定线。因为它包含至少两枚被空位隔开的棋子。所以每个空位至少有一个方向可以直达无穷远，所有可部署位置都属于外部区域。

从外部攻击单点线时没有炮架，无法吃子。攻击连续三枚棋子时，只能用一个端点作炮架吃掉中点。炮落到中点后，水平和垂直方向的四个相邻位置都有黑棋。每条线上又没有第四枚棋子。炮既不能越过相邻棋子移动，也找不到第二枚棋子作为目标。它无法再行动。

于是，在满足前两个条件的局面中，红炮至多吃掉一枚三连中点。若黑将就是中点，可以一步吃掉，答案为 YES；否则永远无法吃到黑将，答案为 NO。结合前面的必要性，判定条件充分且必要。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=100005;
int x[N],y[N],q[N];
bool vis[N];
pair<int,int> a[N];
bool valid(const vector<int> &a)
{
    return a.size()==1||a.size()==3&&a[1]==a[0]+1&&a[2]==a[1]+1;
}
bool check(map<int,vector<int>> &r,map<int,vector<int>> &c,int x,int y,bool &mid)
{
    for(auto &[u,v]:r)
    {
        if(!valid(v))return 0;
        if(v.size()==3)
        {
            int w=v[1];
            if(c[w].size()!=3||c[w][1]!=u)return 0;
            if(u==x&&w==y)mid=1;
        }
    }
    return 1;
}
void solve()
{
    int n;
    cin>>n>>x[0]>>y[0];
    map<int,vector<int>> px,py;
    px[x[0]].push_back(0);
    py[y[0]].push_back(0);
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        px[x[i]].push_back(i);
        py[y[i]].push_back(i);
    }
    int l=0,r=1;
    q[0]=0;
    vis[0]=1;
    while(l<r)
    {
        int u=q[l++];
        for(auto v:px[x[u]])
        {
            if(!vis[v])
            {
                vis[v]=1;
                q[r++]=v;
            }
        }
        px[x[u]].clear();
        for(auto v:py[y[u]])
        {
            if(!vis[v])
            {
                vis[v]=1;
                q[r++]=v;
            }
        }
        py[y[u]].clear();
    }
    int m=0;
    for(int i=0;i<=n;i++)
    {
        if(vis[i])a[m++]={x[i],y[i]};
        vis[i]=0;
    }
    px.clear();
    py.clear();
    for(int i=0;i<m;i++)
    {
        px[a[i].first].push_back(a[i].second);
        py[a[i].second].push_back(a[i].first);
    }
    for(auto &[u,v]:px)sort(v.begin(),v.end());
    for(auto &[u,v]:py)sort(v.begin(),v.end());
    bool mid=0,ok=check(px,py,x[0],y[0],mid)&&check(py,px,y[0],x[0],mid);
    cout<<(ok&&!mid?"NO":"YES")<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}