洛谷P16221 [ECUSTPC 2025] 净化行动题解

思路

可以发现，如果同一行或同一列上有两个及以上黑子，那么白字吃掉其中一个黑子时，另一个黑子会把白子吃掉，此时直接输出NO即可。

否则，考虑求出起点左边第一个有黑子的列、右边第一个有黑子的列、上边第一个有黑子的行、下边第一个有黑子的行，即从起点位置目前可以到达的位置一定是一个矩形。

如果矩形的四个顶点有至少一个是黑子，我们就可以通过斜跳把黑子吃掉。否则，如果矩形的四个顶点没有一个是黑子，白子就走不了了，直接输出NO即可。

代码

#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+5;intt,n;map<int,bool>mp,mpp;structjs{intx,y,id;};vector<js>a,b;boolcmp1(js x,js y){returnx.x<y.x;}boolcmp2(js x,js y){returnx.y<y.y;}boolbj[N];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>t;while(t--){cin>>n;mp.clear(),mpp.clear(),a.clear(),b.clear();intnx,ny;cin>>nx>>ny;for(inti=1;i<=n;i++)bj[i]=0;boolflag=0;for(inti=1;i<=n;i++){intx,y;cin>>x>>y;if(mp[x]||mpp[y])flag=1;a.push_back({x,y,i}),b.push_back({x,y,i}),mp[x]=mpp[y]=1;}sort(a.begin(),a.end(),cmp1);sort(b.begin(),b.end(),cmp2);if(flag){cout<<"NO\n";continue;}intxl=-1,xr=a.size(),yl=-1,yr=b.size(),cnt=n;for(inti=0;i<a.size();i++)if(a[i].x<=nx)xl=i;for(inti=0;i<b.size();i++)if(b[i].y<=ny)yl=i;for(inti=a.size()-1;i>=0;i--)if(a[i].x>=nx)xr=i;for(inti=b.size()-1;i>=0;i--)if(b[i].y>=ny)yr=i;intnum=0;while(cnt--){while(xl>=0&&bj[a[xl].id])xl--;while(yl>=0&&bj[b[yl].id])yl--;while(xr<a.size()&&bj[a[xr].id])xr++;while(yr<b.size()&&bj[b[yr].id])yr++;if(xl>=0&&(yl<0||a[xl].y>=b[yl].y)&&(yr>=b.size()||a[xl].y<=b[yr].y)){bj[a[xl].id]=1,xl--,num++;continue;}if(xr<a.size()&&(yl<0||a[xr].y>=b[yl].y)&&(yr>=b.size()||a[xr].y<=b[yr].y)){bj[a[xr].id]=1,xr++,num++;continue;}if(yl>=0&&(xl<0||a[xl].x<=b[yl].x)&&(xr>=a.size()||a[xr].x>=b[yl].x)){bj[b[yl].id]=1,yl--,num++;continue;}if(yr<b.size()&&(xl<0||a[xl].x<=b[yr].x)&&(xr>=a.size()||a[xr].x>=b[yr].x)){bj[b[yr].id]=1,yr++,num++;continue;}break;}if(num==n)cout<<"YES\n";elsecout<<"NO\n";}return0;}