← 返回题目列表

AtCoder · icpc2015autumn_g

G. 立方体划分

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

问题陈述

Pablo Cubason 是一位著名的立体派艺术家。他正在使用一个长方体制作一件新作品,该长方体由 $A \times B \times C$ 单位立方体组成。他计划通过从长方体中移除 $N$ 单位的立方体来制作一个漂亮的形状。当他准备开始工作时,他注意到通过移除长方体可能会被分成几个彼此不相连的部分。分割长方体是违背他的审美的。所以他想知道他的计划中创造了多少个零件。

你的任务是计算移除$N$个立方体后长方体中连通分量的数量。如果两个立方体共享一个面,则它们是相连的。


输入

输入由单个测试用例组成。 测试用例的格式如下:

$A$$B$$C$$N$
$X_1$ $Y_1$ $Z_1$
...
$X_N$ $Y_N$ $Z_N$

第一行包含四个整数$A$、$B$、$C$ 和$N$。 $A$、$B$ 和 $C$ ($1 \leq A, B, C \leq 10^6$) 表示长方体的大小 --- 长方体从左到右的宽度为 $A$ 单位,从下到上的高度为 $B$ 单位,从前到后的深度为 $C$ 单位。 $N$ ($0 \leq N \leq 20{,}000$, $N \leq A \times B \times C - 1$) 表示 Cubarson 计划中移除的立方体数量。以下 $N$ 行中的每一行都包含三个整数 $X_i$ ($0 \leq X_i \leq A-1$)、$Y_i$ ($0 \leq Y_i \leq B-1$) 和 $Z_i$ ($0 \leq Z_i \leq C-1$)。它们表示位于从左侧第 $X_i$ 个位置、从底部第 $Y_i$ 个位置和从前面第 $Z_i$ 个位置的立方体将在计划中被删除。您可以假设给定的位置是不同的。

输出

打印移除指定立方体后长方体中连通分量的数量。



示例输入 1

2 2 2 4
0 0 0
1 1 0
1 0 1
0 1 1

样本输入 1 的输出

4

示例输入 2

3 3 3 1
1 1 1

样本输入 2 的输出

1

示例输入 3

1 1 3 2
0 0 0
0 0 2

样本输入 3 的输出

1