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

思路可以发现如果同一行或同一列上有两个及以上黑子那么白字吃掉其中一个黑子时另一个黑子会把白子吃掉此时直接输出NO即可。否则考虑求出起点左边第一个有黑子的列、右边第一个有黑子的列、上边第一个有黑子的行、下边第一个有黑子的行即从起点位置目前可以到达的位置一定是一个矩形。如果矩形的四个顶点有至少一个是黑子我们就可以通过斜跳把黑子吃掉。否则如果矩形的四个顶点没有一个是黑子白子就走不了了直接输出NO即可。代码#includebits/stdc.husingnamespacestd;constintN3e55;intt,n;mapint,boolmp,mpp;structjs{intx,y,id;};vectorjsa,b;boolcmp1(js x,js y){returnx.xy.x;}boolcmp2(js x,js y){returnx.yy.y;}boolbj[N];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cint;while(t--){cinn;mp.clear(),mpp.clear(),a.clear(),b.clear();intnx,ny;cinnxny;for(inti1;in;i)bj[i]0;boolflag0;for(inti1;in;i){intx,y;cinxy;if(mp[x]||mpp[y])flag1;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){coutNO\n;continue;}intxl-1,xra.size(),yl-1,yrb.size(),cntn;for(inti0;ia.size();i)if(a[i].xnx)xli;for(inti0;ib.size();i)if(b[i].yny)yli;for(intia.size()-1;i0;i--)if(a[i].xnx)xri;for(intib.size()-1;i0;i--)if(b[i].yny)yri;intnum0;while(cnt--){while(xl0bj[a[xl].id])xl--;while(yl0bj[b[yl].id])yl--;while(xra.size()bj[a[xr].id])xr;while(yrb.size()bj[b[yr].id])yr;if(xl0(yl0||a[xl].yb[yl].y)(yrb.size()||a[xl].yb[yr].y)){bj[a[xl].id]1,xl--,num;continue;}if(xra.size()(yl0||a[xr].yb[yl].y)(yrb.size()||a[xr].yb[yr].y)){bj[a[xr].id]1,xr,num;continue;}if(yl0(xl0||a[xl].xb[yl].x)(xra.size()||a[xr].xb[yl].x)){bj[b[yl].id]1,yl--,num;continue;}if(yrb.size()(xl0||a[xl].xb[yr].x)(xra.size()||a[xr].xb[yr].x)){bj[b[yr].id]1,yr,num;continue;}break;}if(numn)coutYES\n;elsecoutNO\n;}return0;}