← 返回题目列表

AtCoder · arc119_d

D. 网格重画3

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

我们有一个表示为网格的画布 H 行和 W 列。让 (i, j) 表示位于 i从顶部算起的第行 (1 \leq i \leq H) 和 j左起第 列 (1 \leq j \leq W)。最初, (i, j) 被涂成红色,如果 s_{i, j}= R 和蓝色如果 s_{i, j}= B.

对于任意次数,您可以选择以下两个操作之一并执行。

操作X: 选择一个涂成红色的方块,然后将包含该方块(包括其本身)的行中的所有方块重新涂成白色。
操作Y: 选择一个涂成红色的方块,然后将包含该方块(包括其本身)的列中的所有方块重新涂成白色。

展示一种最大化最终涂成白色的方块数量的方法。

约束

  • 1 \leq H \leq 2500
  • 1 \leq W \leq 2500
  • s_{i, j} is R or B. (1 \leq i \leq H, 1 \leq j \leq W)
  • H 和 W 是整数。

输入

输入由标准输入按以下格式给出:

H W
s_{1, 1}s_{1, 2}s_{1, 3}\cdotss_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3}\cdotss_{2, W}
s_{3, 1}s_{3, 2}s_{3, 3}\cdotss_{3, W}
 \vdots
s_{H, 1}s_{H, 2}s_{H, 3}\cdotss_{H, W}

输出

将以下内容打印到标准输出:

n
t_1 r_1 c_1
t_2 r_2 c_2
t_3 r_3 c_3
 \vdots
t_n r_n c_n

在这里, n 是您执行的操作数,并且 t_i, r_i, c_i 意味着您的 i- 第一个操作是操作 t_i 与 (r_i, c_i) 被选中,其中 t_i is X or Y.
如果有多种可能的解决方案,您可以打印其中任何一个。


示例输入 1

4 4
RBBB
BBBB
BBBB
RBRB

示例输出 1

3
X 1 1
Y 4 3
X 4 1

这是一系列操作,使 10 白色方块:

  • 首先,做 操作 X 选择 (1, 1).
  • 然后,做 操作 Y 选择 (4, 3).
  • 然后,做 操作 X 选择 (4, 1).

没有办法使 11 或更多白色方块。


示例输入 2

1 119
BBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBBBBBRBBB

示例输出 2

4
Y 1 60
Y 1 109
Y 1 46
X 1 11

我们可以将所有方块重新漆成白色。


示例输入 3

10 10
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB

示例输出 3

0

由于没有红色方块,我们根本无法进行操作。