← 返回题目列表

Codeforces · 1772/F

F. 副本的副本的副本

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

这一切都从一张黑白图片开始,它可以表示为 $$$n \times m$$$ 矩阵,这样它的所有元素要么是 $$$0$$$ 要么是 $$$1$$$。行的编号从 $$$1$$$ 到 $$$n$$$,列的编号从 $$$1$$$ 到 $$$m$$$。

对图片进行了多次操作(可能为零),分别为以下两种操作之一:

- 选择一个单元格,使其不在边框上(既不是行 $$$1$$$ 或 $$$n$$$,也不是列 $$$1$$$ 或 $$$m$$$),并且它被四个相反颜色的单元格包围(如果是 1,则为四个零,反之亦然),并将其本身涂成相反的颜色;
- 复制当前图片。

请注意,操作的顺序可以是任意的,它们不一定是交替的。

您将看到结果:制作的所有 $$$k$$$ 副本。此外,您还会获得初始图片。然而,所有 $$$k+1$$$ 图片都被打乱。

恢复操作顺序。如果有多个答案,请打印其中任何一个。测试是根据真实的操作顺序构建的,即。 e.至少有一个答案总是存在的。

输入

第一行包含三个整数 $$$n、m$$$ 和 $$$k$$$ ($$$3 \le n, m \le 30$$$; $$$0 \le k \le 100$$$)——分别是图片的行数、列数和复制的数量。

然后是 $$$k+1$$$ 图片 — $$$k$$$ 副本和初始图片。他们的顺序是任意的。

每张图片由$$$n$$$行组成,每行由$$$m$$$个字符组成,每个字符要么是$$$0$$$,要么是$$$1$$$。每张图片前有一个空行。

输出

在第一行中,打印一个整数 - 初始图片的索引。图片按照它们在输入中出现的顺序从 $$$1$$$ 到 $$$k+1$$$ 进行编号。

在第二行中,打印单个整数 $$$q$$$ — 操作数。

接下来的 $$$q$$$ 行应该包含一个操作。应按应用顺序列出操作。每个操作都是以下两种类型之一:

- $$$1$$$ $$$x$$$ $$$y$$$ — 重新着色单元格 $$$(x, y)$$$(第 $$$x$$$ 行中的第 $$$y$$$ 个单元格,它不应该位于边框上,并且应该被四个与自身颜色相反的单元格包围);
- $$$2$$$ $$$i$$$ — 复制当前图片并为其分配索引 $$$i$$$ (索引为 $$$i$$$ 的图片应等于当前图片)。

从 $$$1$$$ 到 $$$k+1$$$ 的每个索引都应该在输出中出现一次——其中一个是初始图片的索引,其余的 $$$k$$$ 是第二类操作的参数。

如果有多个答案,请打印其中任何一个。测试是根据真实的操作顺序构建的,即。 e.至少有一个答案总是存在的。

示例

输入 #1

3 3 1

010
111
010

010
101
010

输出 #1

2
2
1 2 2
2 1

输入 #2

4 5 3

00000
01000
11100
01000

00000
01000
10100
01000

00000
01010
10100
01000

00000
01000
10100
01000

输出 #2

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

输入 #3

5 3 0

110
010
001
011
001

输出 #3

1
0