← 返回题目列表

Codeforces · 327/D

D. 座塔

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

在纸上玩太多之后,Iahub 已经转向电脑游戏。他玩的游戏叫“Block Towers”。它在 n 行 m 列的矩形网格中进行(包含 n × m 个单元)。游戏的目标是建造自己的城市。网格中的一些单元是大洞,Iahub 无法在其中建造任何建筑物。其余单元格为空。在一些空单元中,Iahub 可以精确建造一座以下两种类型的塔:

1. 蓝塔。每个的人口限制等于 100。
2. 红塔。每个单元的人口限制等于 200。但是,只有当至少一个相邻单元具有蓝塔时,才能在某个单元中构建它。两个牢房是邻居,因为它们共享一侧。

Iahub 还可以从任何单元摧毁建筑物。这个手术他想做多少就做多少。摧毁一座建筑物后,其他建筑物不受影响,被摧毁的单元变空(因此如果需要,Iahub可以在该单元中建造一座塔,这种情况请参见第二个示例)。

Iahub 可以说服尽可能多的人进入他的城市。因此他需要配置他的城市以允许尽可能多的人口。因此,他应该找到一系列以最佳方式建造城市的操作序列,以使总人口限制尽可能大。

他说他是这个游戏中最好的,但他没有最优解。编写一个程序来计算最佳的,以向他表明他并不像他想象的那么好。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 500)。接下来的 n 行每行包含 m 个字符,描述网格。第 i 行中的第 j 个字符是“.”如果你被允许在坐标(i,j)的单元格上建造一座塔(空单元格),或者如果那里有一个大洞,则建造“#”。

输出

在第一行打印一个整数 k (0 ≤ k ≤ 106) — Iahub 为获得最佳结果而应执行的操作数。

以下 k 行中的每一行必须包含以下格式的单个操作:

1. «B x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — 在单元格(x, y)处建造一座蓝色塔;
2. «R x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — 在单元格 (x, y) 处建造一座红塔;
3. «D x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — 摧毁单元 (x, y) 处的一座塔。

如果有多个解决方案,您可以输出其中任何一个。请注意,您不应该最小化操作数量。

示例

输入 #1

2 3
..#
.#.

输出 #1

4
B 1 1
R 1 2
R 2 1
B 2 3

输入 #2

1 3
...

输出 #2

5
B 1 1
B 1 2
R 1 3
D 1 2
R 1 2