CF1054E Chips Puzzle

Egor 想出了一个新的棋子谜题，并邀请你来玩。 该谜题的形式为一个有 $n$ 行 $m$ 列的表格，每个格子中可以按顺序放置若干个黑色或白色棋子。因此，每个格子的状态可以用一个由字符 '0'（白棋子）和 '1'（黑棋子）组成的字符串描述，字符串可能为空。整个谜题可以用一个表格描述，其中每个格子是一个由 0 和 1 组成的字符串。你的任务是将谜题从一种状态变换到另一种状态。 你可以使用如下操作： - 选择两个不同的格子 $(x_1, y_1)$ 和 $(x_2, y_2)$，这两个格子必须在同一行或同一列，并且格子 $(x_1, y_1)$ 中的字符串必须非空； - 在一次操作中，你可以将格子 $(x_1, y_1)$ 中字符串的最后一个字符移动到格子 $(x_2, y_2)$ 的字符串开头。 Egor 为你准备了两个表格状态：初始状态和目标状态。保证两个表格中的 0 和 1 的数量相同。你的目标是通过若干次操作，将初始状态变换为目标状态。当然，Egor 不希望操作次数太多。设 $s$ 为每个表格中字符的总数（两者相同），你需要在不超过 $4 \cdot s$ 次操作内完成变换。

第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 300$），分别表示表格的行数和列数。 接下来的 $n$ 行描述初始状态，每行包含 $m$ 个非空的由 0 和 1 组成的字符串。在第 $i$ 行中，第 $j$ 个字符串表示格子 $(i, j)$ 的内容。行从 $1$ 到 $n$ 编号，列从 $1$ 到 $m$ 编号。 再接下来的 $n$ 行以相同格式描述目标状态。 设初始状态所有字符串的总长度为 $s$。保证 $s \leq 100\,000$。同时保证初始状态和目标状态中 0 和 1 的数量相同。

第一行输出 $q$，表示你所用的操作次数。你需要找到一个满足 $0 \leq q \leq 4 \cdot s$ 的解。 接下来的 $q$ 行，每行输出四个整数 $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)$ 格子的字符串必须非空。你给出的操作序列应能将初始状态变换为目标状态。 保证一定存在解。如果有多种方案，输出任意一种即可。

考虑第一个样例。 - 当前表格状态： 00 10 01 11 第一步操作。格子 $(2, 1)$ 中的字符串为 $01$。对 $(2, 1)$ 和 $(1, 1)$ 执行操作，将 $01$ 的末尾 $1$ 移到 $00$ 的开头，得到 $100$。 - 当前表格状态： 100 10 0 11 第二步操作。格子 $(1, 1)$ 中的字符串为 $100$。对 $(1, 1)$ 和 $(1, 2)$ 执行操作，将 $100$ 的末尾 $0$ 移到 $10$ 的开头，得到 $010$。 - 当前表格状态： 10 010 0 11 第三步操作。格子 $(1, 2)$ 中的字符串为 $010$。对 $(1, 2)$ 和 $(2, 2)$ 执行操作，将 $010$ 的末尾 $0$ 移到 $11$ 的开头，得到 $011$。 - 当前表格状态： 10 01 0 011 第四步操作。格子 $(2, 2)$ 中的字符串为 $011$。对 $(2, 2)$ 和 $(2, 1)$ 执行操作，将 $011$ 的末尾 $1$ 移到 $0$ 的开头，得到 $10$。 - 当前表格状态： 10 01 10 01 很容易看出，我们已经达到了目标状态。 由 ChatGPT 4.1 翻译