对每个红格的行和列连边,建出二分图。对于二分图中的每个连通块分别考虑。
大胆猜测对于每个连通块,我们都能够进行适当的操作,使得只有一行/一列没被操作(显然不能使所有行和列都被操作)。对应的方案就是随便取一棵生成树,把不被染白的那一行/列拎出来当根,然后自底向上,每次把儿子的那一行/列染白。容易发现儿子的操作不会让父亲无法操作。
现在问题变成了对于每个连通块选择扔掉一行还是扔掉一列。设 \(a,b\) 分别为染白的行数和列数,那么最终被染白的格子为 \(nm - (n-a)(m-b)\)。根据小奥的和一定,差小积大,我们要让 \(n-a\) 和 \(m-b\) 的差尽量大。显然最优方案中 \(a,b\) 必然有一个是 \(0\),比较一下哪个差大即可。
code
// Problem: D - Grid Repainting 3
// Contest: AtCoder - AtCoder Regular Contest 119
// URL: https://atcoder.jp/contests/arc119/tasks/arc119_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2510;
int n, m, head[maxn << 1], len;
char s[maxn][maxn];
bool vis1[maxn], vis2[maxn], vis[maxn << 1];
struct edge {
int to, next;
} edges[maxn * maxn * 5];
inline void add_edge(int u, int v) {
edges[++len].to = v;
edges[len].next = head[u];
head[u] = len;
}
struct node {
int op, x, y;
node(int a = 0, int b = 0, int c = 0) : op(a), x(b), y(c) {}
};
vector<node> ans;
void dfs(int u) {
vis[u] = 1;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (!vis[v]) {
dfs(v);
if (v <= n) {
ans.pb(1, v, u - n);
} else {
ans.pb(2, u, v - n);
}
}
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i] + 1);
for (int j = 1; j <= m; ++j) {
if (s[i][j] == 'R') {
vis1[i] = vis2[j] = 1;
add_edge(i, j + n);
add_edge(j + n, i);
}
}
}
int e1 = 0, e2 = 0;
for (int i = 1; i <= n; ++i) {
e1 += (!vis1[i]);
}
for (int i = 1; i <= m; ++i) {
e2 += (!vis2[i]);
}
mems(vis, 0);
if (e1 > e2) {
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs(i);
}
}
} else {
for (int i = n + 1; i <= n + m; ++i) {
if (!vis[i]) {
dfs(i);
}
}
}
printf("%d\n", (int)ans.size());
for (node u : ans) {
printf("%c %d %d\n", u.op == 1 ? 'X' : 'Y', u.x, u.y);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Repainting AtCoder Regular Contest Gridrepainting atcoder regular contest repainting atcoder 119d grid atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest builder