P3341 [ZJOI2014] 消棋子

挺简单的一道题目，代码实现比较复杂。

第一问

每一行，每一列用 \(set\) 维护，直接模拟

第二问

考虑贪心，一对点删了一定比没删优，所以可以先枚举那些点对可以直接删除。
然后考虑一对点删除了之后又那些点对可能会从不能删变成能删。
显然，对于删掉的两个点，祂们分别向上，向下，向左，向右碰到的第一个点所在的点对是有可能发生从不能删变成能删的，最多 \(8\) 个点，直接枚举。

代码

/*
Luogu P3341 [ZJOI2014] 消棋子
2026-03-23
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=100010,inf=1000000000;
int r,c,n;
bool vis[maxn];
struct Point{int x,y,id;}col[maxn][2],w[maxn*2];
struct node{
    set<pair<int,int>>s;
    int get_nxt(int x){
        auto w=s.lower_bound({x,0});
        if(w==s.end()) return 0;
        if(w->first==x) return 0;
        return w->second;
    }
    int get_pre(int x){
        auto w=s.lower_bound({x,inf});
        if(w==s.begin()) return 0;
        w--;
        if(w->first==x) return 0;
        return w->second;
    }
    void del(int x){s.erase(s.lower_bound({x,0}));}
}rw[maxn],cu[maxn];
int get_color(int x,int y,char fx){
    if(fx=='L') return rw[x].get_pre(y);
    if(fx=='R') return rw[x].get_nxt(y);
    if(fx=='U') return cu[y].get_pre(x);
    return cu[y].get_nxt(x);
}
void del(int x,int y){rw[x].del(y),cu[y].del(x);}
vector<tuple<int,int,char,char>>vt_for_out;
tuple<int,int,char,char>check(int co){
    int x=w[co<<1].x,y=w[co<<1].y,xx=w[co<<1|1].x,yy=w[co<<1|1].y;
    if(x==xx){
        if(y>yy) swap(y,yy);
        if(rw[x].get_nxt(y+1)==co) return{x,y+1,'L','R'};
        return{0,0,0,0};
    }
    if(y==yy){
        if(x>xx) swap(x,xx);
        if(cu[y].get_nxt(x+1)==co) return{x+1,y,'U','D'};
        return{0,0,0,0};
    }
    if(x>xx) swap(x,xx),swap(y,yy);
    if(y<=yy){
        if(get_color(xx,y,'U')==co&&get_color(xx,y,'R')==co) return{xx,y,'U','R'};
        if(get_color(x,yy,'L')==co&&get_color(x,yy,'D')==co) return{x,yy,'L','D'};
        return{0,0,0,0};
    }
    if(get_color(xx,y,'U')==co&&get_color(xx,y,'L')==co) return{xx,y,'U','L'};
    if(get_color(x,yy,'R')==co&&get_color(x,yy,'D')==co) return{x,yy,'R','D'};
    return{0,0,0,0};
}
signed main(){
    read(r,c,n);
    for(int i=1;i<=n;i++){
        read(col[i][0].x,col[i][0].y,col[i][1].x,col[i][1].y);
        col[i][0].id=col[i][1].id=i;
        w[i<<1]=col[i][0],w[i<<1|1]=col[i][1];
    }
    for(int i=2;i<=n*2+1;i++) rw[w[i].x].s.insert({w[i].y,w[i].id}),cu[w[i].y].s.insert({w[i].x,w[i].id});
    int m;read(m);
    for(int i=1;i<=m;i++){
        int x,y;char op1,op2;read(x,y,op1,op2);
        int a=get_color(x,y,op1),b=get_color(x,y,op2);
        if(!a||a!=b) continue;
        vt_for_out.push_back({x,y,op1,op2});
        del(w[a<<1].x,w[a<<1].y),del(w[a<<1|1].x,w[a<<1|1].y);
        vis[a]=1;
    }
    write(vt_for_out.size()),write("\n");
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        auto x=check(i);
        if(get<0>(x)==0) continue;
        vt_for_out.push_back(x);
        del(w[i<<1].x,w[i<<1].y),del(w[i<<1|1].x,w[i<<1|1].y);
        vis[i]=1,q.push(i);
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        auto insert=[&q](int co){
            if(vis[co]||!co) return ;
            auto x=check(co);
            if(get<0>(x)==0) return ;
            vt_for_out.push_back(x);
            del(w[co<<1].x,w[co<<1].y),del(w[co<<1|1].x,w[co<<1|1].y);
            vis[co]=1,q.push(co);
        };
        int x=w[u<<1].x,y=w[u<<1].y;
        insert(get_color(x,y,'U'));
        insert(get_color(x,y,'D'));
        insert(get_color(x,y,'L'));
        insert(get_color(x,y,'R'));
        x=w[u<<1|1].x,y=w[u<<1|1].y;
        insert(get_color(x,y,'U'));
        insert(get_color(x,y,'D'));
        insert(get_color(x,y,'L'));
        insert(get_color(x,y,'R'));
    }
    write(vt_for_out.size()),write("\n");
    for(auto[a,b,c,d]:vt_for_out) write(a,b,c,d);
    return 0;
}