← 返回题目列表

Codeforces · 1054/E

E. 筹码拼图

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

Egor 提出了一个新的筹码拼图并建议您玩。

拼图采用表格形式,包含 $$$n$$$ 行和 $$$m$$$ 列,每个单元格可以包含数个排成一行的黑色或白色筹码。因此,单元的状态可以用由字符“0”(白色芯片)和“1”(黑色芯片)组成的字符串来描述,可能是空的,整个拼图可以描述为一个表格,其中每个单元都是一串由 0 和 1 组成的字符串。任务是从拼图的一种状态得到另一种状态。

为此,您可以使用以下操作。

- 选择2个不同的单元格$$$(x_1, y_1)$$$和$$$(x_2, y_2)$$$:单元格必须位于表格的同一行或同一列,并且单元格$$$(x_1, y_1)$$$中的字符串必须非空;
- 在一次操作中,您可以将单元格 $$$(x_1, y_1)$$$ 处的字符串的最后一个字符移动到单元格 $$$(x_2, y_2)$$$ 处的字符串开头。

Egor 为您提出了表格的两种状态:初始状态和最终状态。保证表中 0 和 1 的数量相同。您的目标是通过多个操作从初始状态获得最终状态。当然,叶戈尔不希望操作次数非常多。我们将每个表中的字符数表示为 $$$s$$$(它们是相同的)。那么你应该使用不超过 $$$4 \cdot s$$$ 操作。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n, m \leq 300$$$) — 分别是表的行数和列数。

以下 $$$n$$$ 行按以下格式描述表的初始状态:每行包含 $$$m$$$ 由零和一组成的非空字符串。在这些行的第 $$$i$$$ 中,第 $$$j$$$ 字符串是在单元格 $$$(i, j)$$$ 处写入的字符串。行从 $$$1$$$ 到 $$$n$$$ 进行计数,列从 $$$1$$$ 到 $$$m$$$ 进行计数。

以下 $$$n$$$ 行以相同的格式描述了表的最终状态。

让我们将初始状态下字符串的总长度表示为$$$s$$$。保证 $$$s \leq 100\, 000$$$。还保证初始状态和最终状态下零和一的数量一致。

输出

在第一行打印 $$$q$$$ — 使用的操作数。您应该找到这样的解决方案 $$$0 \leq q \leq 4 \cdot s$$$。

在接下来的 $$$q$$$ 行中,打印 4 个整数 $$$x_1$$$、$$$y_1$$$、$$$x_2$$$、$$$y_2$$$。在第 $$$i$$$ 行上,您应该打印第 $$$i$$$ 操作的描述。这些整数应满足条件 $$$1 \leq x_1, x_2 \leq n$$$, $$$1 \leq y_1, y_2 \leq m$$$, $$$(x_1, y_1) \neq (x_2, y_2)$$$, $$$x_1 = x_2$$$ 或 $$$y_1 = y_2$$$。单元格 $$$(x_1, y_1)$$$ 中的字符串应该非空。这一系列操作应该将表的初始状态转换为最终状态。

我们可以证明存在一个解决方案。如果有多个解决方案,请找到其中任何一个。

示例

输入 #1

2 2
00 10
01 11
10 01
10 01

输出 #1

4
2 1 1 1
1 1 1 2
1 2 2 2
2 2 2 1

输入 #2

2 3
0 0 0
011 1 0
0 0 1
011 0 0

输出 #2

4
2 2 1 2
1 2 2 2
1 2 1 3
1 3 1 2

注意

考虑第一个例子。

- 表的当前状态:00 1001 11 第一次操作。单元格 $$$(2, 1)$$$ 包含字符串 $$$01$$$。将运算应用于单元格 $$$(2, 1)$$$ 和 $$$(1, 1)$$$,我们将 $$$1$$$ 从字符串 $$$01$$$ 的末尾移动到字符串 $$$00$$$ 的开头,并得到字符串 $$$100$$$。
- 表的当前状态:100 100 11 第二次操作。单元格 $$$(1, 1)$$$ 包含字符串 $$$100$$$。将运算应用于单元格 $$$(1, 1)$$$ 和 $$$(1, 2)$$$,我们将 $$$0$$$ 从字符串 $$$100$$$ 的末尾移动到字符串 $$$10$$$ 的开头,并得到字符串 $$$010$$$。
- 表的当前状态:10 0100 11 第三次操作。单元格 $$$(1, 2)$$$ 包含字符串 $$$010$$$。将运算应用于单元格 $$$(1, 2)$$$ 和 $$$(2, 2)$$$,我们将 $$$0$$$ 从字符串 $$$010$$$ 的末尾移动到字符串 $$$11$$$ 的开头,并得到字符串 $$$011$$$。
- 表的当前状态:10 010 011 第四次操作。单元格 $$$(2, 2)$$$ 包含字符串 $$$011$$$。将运算应用于单元格 $$$(2, 2)$$$ 和 $$$(2, 1)$$$,我们将 $$$1$$$ 从字符串 $$$011$$$ 的末尾移动到字符串 $$$0$$$ 的开头,并得到字符串 $$$10$$$。
- 表的当前状态:10 0110 01

很容易看出我们已经达到了表的最终状态。