← 返回题目列表

Codeforces · 1965/E

E. 连接的立方体

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

当前有 $$$n \cdot m$$$ 个单位立方体位于 $$$(1, 1, 1)$$$ 到 $$$(n, m, 1)$$$ 位置。每个立方体都是 $$$k$$$ 颜色之一。您想要在任何整数坐标处添加额外的立方体,以便每种颜色的立方体子集相连,其中如果两个立方体共享一个面,则认为它们是相连的。

换句话说,对于每对相同颜色 $$$c$$$ 的立方体,应该可以从一个立方体移动到另一个立方体,仅穿过共享一个面的颜色 $$$c$$$ 的立方体。

现有的立方体当前位于房间的角落里。有无色立方体完全填充平面 $$$x = 0$$$、$$$y = 0$$$ 和 $$$z = 0$$$,防止您在此处或任何负坐标处放置额外的立方体。

找到一个最多使用 $$$4 \cdot 10^5$$$ 个额外立方体(不包括当前存在的立方体)的解,或者确定没有解。可以证明,在给定的约束下,如果有一个解决方案,则最多使用 $$$4 \cdot 10^5$$$ 额外的立方体。

输入

输入的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n, m, k \le 50$$$) - 分别是立方体的行数和列数以及颜色数。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含 $$$m$$$ 个整数。其中第 $$$j$$$ 是 $$$a_{ij}$$$ ($$$1 \le a_{ij} \le k$$$) — 位置 $$$(i, j, 1)$$$ 处立方体的颜色。对于从 $$$1$$$ 到 $$$k$$$ 的每种颜色,保证该颜色的输入中至少有一个立方体。

输出

如果没有解决方案,则打印单个整数 $$$-1$$$。

否则,输出的第一行应包含一个整数 $$$p$$$ ($$$0 \le p \le 4 \cdot 10^5$$$) - 您将添加的额外立方体的数量。

接下来的 $$$p$$$ 行应包含四个整数 $$$x$$$、$$$y$$$、$$$z$$$ 和 $$$c$$$ ($$$1 \le x, y, z \le 10^6$$$, $$$1 \le c \le k$$$) - 指示您要在位置添加颜色为 $$$c$$$ 的立方体$$$(x,y,z)$$$。

输出中的两个立方体不应具有相同的坐标,并且输出中的任何立方体不应与输入中的任何立方体具有相同的坐标。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

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

输出 #1

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

输入 #2

2 2 2
2 1
1 2

输出 #2

9
1 3 1 1
2 3 1 1
3 1 1 1
3 2 1 1
3 3 1 1
1 1 2 2
1 2 2 2
2 1 2 2
2 2 2 2

注意

语句中的图像对应于第一个示例情况,其中 $$$\text{red} = 1$$$、$$$\text{blue} = 2$$$、$$$\text{green} = 3$$$。