← 返回题目列表

Codeforces · 2207/G

G. 无牙仔

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

禁忌的友谊 — 约翰·鲍威尔,《驯龙高手》

设 $$$n, m, a, b$$$ 为正整数,$$$a \leq b$$$。无牙正在 $$$n \times m$$$ 的沙子网格中画画,沙子最初是全白色的。他可能会一步执行以下操作:

  • 选择任何当前白色的单元格,如果其边缘相邻的邻居中最多有一个黑色单元格,则将其涂成黑色。

因为无牙对自己的艺术很挑剔,所以他认为网格中的一些单元格是 有需要的,这些单元格最终必须变成黑色。在不需要的细胞中,他还认为其中一些是 特别。如果单元格特殊,则其值为 $$$b$$$,否则为 $$$a$$$。 没有特殊的单元格与有需要的单元格接壤。

设 $$$P$$$ 为网格中所有单元格值的总和 不是 有需要的。由于无牙对他的艺术非常讲究,他想要做出一些举动,例如:

  • 所有动作完成后,每个有需要的单元格都会变黑,
  • 黑色单元格的总值 (包括 需要的细胞)至少为 $$$\frac{2}{3} \cdot P$$$。

计算无牙仔可以采取的任何行动顺序。测试以这样的方式生成,保证输入中的所有有需要的单元格在经过一定次数的移动后都可以变成黑色。此外,可以证明,对于给定的约束,总是存在令人满意的移动序列。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 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$$$ 行中的第 $$$i$$$ 行各包含一个字符串 $$$s_i$$$ — 一个由 $$$m$$$ 个字符组成的字符串,描述第 $$$i$$$ 行单元格。

  • 第 $$$j$$$ 个字符是 '#' 如果 $$$(i, j)$$$ 处的单元格有需要。
  • 第 $$$j$$$ 个字符是 'x' 如果 $$$(i, j)$$$ 处的单元格是特殊的。
  • 否则,第 $$$j$$$ 个字符是 '.'.
保证没有需要的小区与特殊小区相邻。

测试以这样的方式生成,保证输入中的所有有需要的单元格在经过一定次数的移动后都可以变成黑色。

保证所有测试用例的 $$$(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)$$$ 处的单元格着色为黑色。

示例

输入
复制

3
3 3 1 5
#..
...
..x
2 3 1 2
...
xxx
3 5 8 9
x.x.x
.x.x.
x.#.x

输出
复制

6
1 1
3 1
3 2
3 3
2 3
1 3
3
2 1
2 2
2 3
10
1 1
1 2
1 3
2 2
2 5
1 5
3 5
2 4
3 3
3 1

注意

在第一个测试用例中,左上角有一个需要的单元格,右下角有一个特殊的单元格。使用示例输出中的操作,我们最终将得到以下网格:

在不需要的单元格中,有 $$$7$$$ 非特殊单元格每个价值 $$$1$$$,$$$1$$$ 特殊单元格价值 $$$5$$$,因此 $$$P = 12$$$。因此,我们需要对总价值至少为 $$$\frac{2}{3} \cdot 12 = 8$$$ 的单元格进行着色;给定的移动序列达到的值是$$$10$$$。

在第二个测试用例中,没有需要的单元格,但在底行单元格中有三个特殊单元格。使用示例输出中的操作,我们最终将得到以下网格:

有$$$3$$$非特殊单元格每个价值$$$1$$$,$$$3$$$特殊单元格价值$$$2$$$,所以$$$P = 9$$$。因此,我们需要对总价值至少为 $$$\frac{2}{3} \cdot 9 = 6$$$ 的单元格进行着色;给定的移动序列达到的值是$$$6$$$。

在第三个测试用例中,$$$(3, 3)$$$ 处有一个需要的单元格,以及 $$$7$$$ 特殊单元格。使用示例输出中的操作,我们最终将得到以下网格:

在不需要的单元格中,有 $$$7$$$ 非特殊单元格每个价值 $$$8$$$ 和 $$$7$$$ 特殊单元格价值 $$$9$$$,因此 $$$P = 7 \cdot 8 + 7 \cdot 9 = 119$$$。因此,我们需要对总价值至少为 $$$\frac{2}{3} \cdot 119 = 79 \frac{1}{3}$$$ 的单元格进行着色;给定的移动序列达到的值是$$$87$$$。