CF327D Block Tower

在玩够了纸上游戏之后，Iahub 转而玩起了电脑游戏。他正在玩的游戏叫做「Block Towers」。该游戏在一个 $n$ 行 $m$ 列的矩形网格上进行（包含 $n \times m$ 个格子）。游戏的目标是建造属于你自己的城市。网格中的某些格子是大坑，Iahub 不能在这些地方建造任何建筑。其余格子为空地，Iahub 可以在某个空地上建造且仅能建造一座下述两种塔中的一种： 1. 蓝塔。每个蓝塔的人口上限为 $100$。 2. 红塔。每个红塔的人口上限为 $200$。但只有在该格子至少有一个相邻格子（共享一条边的格子）存在蓝塔时，才可以建造红塔。 Iahub 还可以在任意格子上摧毁建筑。他可以进行任意多次该操作。被摧毁后，除了该格子的建筑之外，其他建筑不会受到影响，被摧毁的格子会变为空地（因此之后可以在该格子上建塔，见第二个样例）。 Iahub 可以说服任意数量的人口来到他的城市。因此，他需要规划出一种城市建造顺序，使得最大人口上限尽可能大。请你找出一种操作顺序，使得总人口上限最大，以此证明他的游戏水平并非最佳。

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 500$）。接下来的 $n$ 行每行包含 $m$ 个字符，描述网格。第 $i$ 行第 $j$ 个字符为 '.' 表示该位置 $(i, j)$ 是空地，可以建塔；为 '#' 表示该位置有大坑，无法建塔。

输出第一行一个整数 $k$（$0 \leq k \leq 10^6$），表示 Iahub 需要执行的操作数以获得最大人口上限。 接下来的 $k$ 行，每行表示一个操作，格式如下： 1. "B x y"（$1\leq x\leq n, 1\leq y\leq m$）——表示在 $(x, y)$ 地点建造一座蓝塔； 2. "R x y"（$1\leq x\leq n, 1\leq y\leq m$）——表示在 $(x, y)$ 地点建造一座红塔； 3. "D x y"（$1\leq x\leq n, 1\leq y\leq m$）——表示摧毁 $(x, y)$ 位置上的塔。 如果有多组满足条件的方案，你可以输出任意一组。注意，并不要求操作数最少。

由 ChatGPT 5 翻译