CF2207G.Toothless

Forbidden Friendship — John Powell, How To Train Your Dragon

设 $n, m, a, b$ 为正整数，且 $a \leq b$。Toothless 正在一个 $n \times m$ 的沙地网格上作画，初始时所有格子都是白色。每一步操作中，他可以执行如下操作：

• 任选一个当前为白色的格子，如果这个格子的相邻（上下左右）格子中有不多于 $1$ 个为黑色，则将其涂黑。

因为 Toothless 对自己的艺术很讲究，所以他认为网格中有些格子是“必需”的，这些格子最终必须变成黑色。在非必需格子中，他又觉得有些格子是“特殊”的。如果一个格子是特殊的，则该格子的价值为 $b$，否则价值为 $a$。不存在任何特殊格子和必需格子通过边相邻。

设 $P$ 为网格中所有非必需格子的价值之和。因为 Toothless 对艺术极其讲究，他希望你设计一系列操作，使得：

• 所有必需的格子全部变黑；
• 所有被涂黑的格子（包括必需格子）总价值之和不少于 $\frac{2}{3} \cdot P$。

请输出一组合法操作序列。数据保证输入中的所有必需格子都可通过若干次操作变为黑色。此外，可以证明一定存在满足上述条件的操作序列。

每组测试包含多个测试用例。第一行是测试用例组数 $t$（$1 \leq t \leq 10^4$）。每个测试用例描述如下。

每个测试用例的第一行包含四个整数 $n$、$m$、$a$ 和 $b$（$1 \leq n, m \leq 2 \cdot 10^3$，$1 \leq n \cdot m \leq 2 \cdot 10^3$，$1 \leq a \leq b \leq 5 \cdot 10^5$）——分别为网格的行数和列数以及非特殊格子的价值、特殊格子的价值。

接下来 $n$ 行，每行给出一个字符串 $s_i$，每个长度正好为 $m$，表示第 $i$ 行各个格子的类型：

• 如果第 $j$ 列的字符为 '#'，则 $(i, j)$ 位置为必需格子；
• 如果为 'x'，则为特殊格子；
• 否则为 '.'，表示普通格子。

保证不存在任意一个特殊格子与必需格子为边相邻。数据保证所有必需格子可以按题面描述被涂黑。

保证所有测试用例中 $(nm)^2$ 的总和不超过 $4 \cdot 10^6$。

对于每个测试用例，输出如下内容：

第一行输出操作步数 $op$（$0 \leq op \leq n \cdot m$）。

接下来 $op$ 行，每行输出两个整数 $i, j$（$1 \leq i \leq n, 1 \leq j \leq m$），表示第 $i$ 行第 $j$ 列的格子被涂黑。

在第一个样例中，左上角有一个必需格子，右下角有一个特殊格子。示例输出给出的方案执行后，网格变为：

非必需格子中，有 $7$ 个普通格子，价值 $1$，$1$ 个特殊格子，价值 $5$，所以 $P = 12$。需要黑格价值和不少于 $\frac{2}{3} \cdot 12 = 8$，而输出序列取得了 $10$。

第二个样例没有必需格子，但底行有三个特殊格子。输出方案变为：

有 $3$ 个普通格子，价值 $1$，$3$ 个特殊格子，价值 $2$，所以 $P = 9$，需要黑格价值和不少于 $6$，输出方案取得了 $6$。

第三个样例，第 $(3,3)$ 有个必需格子，且有 $7$ 个特殊格子。输出方案：

非必需格子中，有 $7$ 个普通格子价值 $8$，$7$ 个特殊格子价值 $9$，所以 $P = 7 \cdot 8 + 7 \cdot 9 = 119$。需要黑格价值和不少于 $79 \frac{1}{3}$，输出序列取得了 $87$。

由 ChatGPT 5 翻译