题意

有 $n$ 行 $m$ 列的棋盘，每个位置颜色一开始是红色或蓝色。每次操作你可以选择一个红色格子，选择将这个格子所在行/列都涂成白色格子。求构造一组最大化白色格子的方案。

$n,m \leq 2500$。

题解

比赛的时候没有尝试往二分图上去想，因为感觉这种带先后覆盖顺序的问题好像不是很能做，但是事实证明错了。。

这种每次覆盖一行，或者一列的做法都考虑将行列抽象成点，操作位置抽象成边。对于这个题，就是一个边可以指定它连接的一个点，将这个点和其相邻的边删去。

考虑一个联通块怎么做：一定可以找出一个联通块的生成树，然后我们自底向上每次删去叶子就好了。我们发现这样我们最后只会删不了根。

也就是说，我们要决策根是一个行优还是一个列优。暴力的做法是都做一遍取最大值，但是我们其实可以考虑一下，如果一个行/列作为根会损失多少：如果全选行为根，损失的就是这一行上没有红色的列的个数；列同理。所以我们统计没有红色的行的个数 $r_1$，和没有红色的列的个数 $r_2$。如果 $r_1 < r_2$，说明选列为根的代价小，就每次选择一个列开始 bfs 就可以。否则就选行。

bfs 的过程就是，我们将每个边（也就是对应原图中的一个红色位置）对应到操作它的叶子代表的行/列。最后加入答案的时候要倒着加即可。

总结：遇到行列问题还是要多思考二分图。

代码

#include <bits/stdc++.h>

#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2500 + 5;
std::vector<int> G[MAXN<<1];
int n,m;
char str[MAXN][MAXN];
int pre[MAXN<<1];
bool vis[MAXN<<1];

int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) scanf("%s",str[i]+1);
    FOR(i,1,n) FOR(j,1,m) if(str[i][j] == 'R') G[i].pb(n+j),G[n+j].pb(i);
    int r1 = 0,r2 = 0;
    // r1: 空行的个数 = 废弃一个列的个数
    // r2: 空列的个数 = 废弃一个行的个数
    FOR(i,1,n){
        int c = 0;
        FOR(j,1,m) c += (str[i][j] == 'R');
        if(!c) ++r1;
    }
    FOR(i,1,m){
        int c = 0;
        FOR(j,1,n) c += (str[j][i] == 'R');
        if(!c) ++r2;
    }
    std::vector<int> ans;
    auto bfs = [&](int s){
        if(vis[s]) return;
        std::vector<int> tmp;
        std::queue<int> q;q.push(s);vis[s] = 1;
        while(!q.empty()){
            int v = q.front();q.pop();
            for(auto x:G[v]){
                if(!vis[x]){
                    tmp.pb(x);pre[x] = v;
                    q.push(x);vis[x] = 1;
                }
            }
        }
        std::reverse(all(tmp));
        for(auto x:tmp) ans.pb(x);
    };
    if(r1 < r2) FOR(i,n+1,n+m) bfs(i);
    else FOR(i,1,n) bfs(i);
    printf("%d\n",SZ(ans));
    for(auto x:ans){
        if(x <= n){
            printf("X %d %d\n",x,pre[x]-n);
        }
        else{
            printf("Y %d %d\n",pre[x],x-n);
        }
    }
    return 0;
}