CF638D.Three-dimensional Turtle Super Computer
普及+/提高
通过率:0%
时间限制:3.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
A super computer has been built in the Turtle Academy of Sciences. The computer consists of n·m·k CPUs. The architecture was the paralellepiped of size n × m × k, split into 1 × 1 × 1 cells, each cell contains exactly one CPU. Thus, each CPU can be simultaneously identified as a group of three numbers from the layer number from 1 to n, the line number from 1 to m and the column number from 1 to k.
In the process of the Super Computer's work the CPUs can send each other messages by the famous turtle scheme: CPU (x, y, z) can send messages to CPUs (x + 1, y, z), (x, y + 1, z) and (x, y, z + 1) (of course, if they exist), there is no feedback, that is, CPUs (x + 1, y, z), (x, y + 1, z) and (x, y, z + 1) cannot send messages to CPU (x, y, z).
Over time some CPUs broke down and stopped working. Such CPUs cannot send messages, receive messages or serve as intermediates in transmitting messages. We will say that CPU (a, b, c) controls CPU (d, e, f) , if there is a chain of CPUs (x__i, y__i, z__i), such that (_x_1 = a, _y_1 = b, _z_1 = c), (x__p = d, y__p = e, z__p = f) (here and below p is the length of the chain) and the CPU in the chain with number i (i < p) can send messages to CPU i + 1.
Turtles are quite concerned about the denial-proofness of the system of communication between the remaining CPUs. For that they want to know the number of critical CPUs. A CPU (x, y, z) is critical, if turning it off will disrupt some control, that is, if there are two distinctive from (x, y, z) CPUs: (a, b, c) and (d, e, f), such that (a, b, c) controls (d, e, f) before (x, y, z) is turned off and stopped controlling it after the turning off.
一台超级计算机已在龟类科学院建成。该计算机由 n⋅m⋅k 个 CPU 组成。其架构为一个尺寸为 n×m×k 的长方体,被划分为 1×1×1 的小单元格,每个单元格中恰好包含一个 CPU。因此,每个 CPU 可由一组三个数唯一标识:层数(从 1 到 n)、行号(从 1 到 m)和列号(从 1 到 k)。
在超级计算机运行过程中,CPU 之间可通过著名的“龟式通信方案”相互发送消息:CPU (x,y,z) 可向 CPU (x+1,y,z)、(x,y+1,z) 和 (x,y,z+1)(当然,仅当这些 CPU 存在时)发送消息;该通信是单向的,即 CPU (x+1,y,z)、(x,y+1,z) 和 (x,y,z+1) 不能 向 CPU (x,y,z) 发送消息。
随着时间推移,部分 CPU 损坏并停止工作。此类故障 CPU 既不能发送消息,也不能接收消息,亦不能作为消息传递的中间节点。我们称 CPU (a,b,c) 控制 CPU (d,e,f),若存在一条 CPU 序列 (xi,yi,zi),满足:
- (x1,y1,z1)=(a,b,c),
- (xp,yp,zp)=(d,e,f)(此处及后文 p 表示该序列的长度),
- 对任意 i<p,序列中第 i 个 CPU 可向第 i+1 个 CPU 发送消息。
龟类学者十分关注剩余 CPU 间通信系统的容错能力。为此,他们希望计算出关键 CPU 的数量。一个 CPU (x,y,z) 被称为关键 CPU,当且仅当关闭它将导致某条控制关系被破坏,即:存在两个不同于 (x,y,z) 的 CPU (a,b,c) 和 (d,e,f),使得在 (x,y,z) 关闭前,(a,b,c) 控制 (d,e,f);而在 (x,y,z) 关闭后,(a,b,c) 不再控制 (d,e,f)。
输入格式
The first line contains three integers n, m and k (1 ≤ n, m, k ≤ 100) — the dimensions of the Super Computer.
Then n blocks follow, describing the current state of the processes. The blocks correspond to the layers of the Super Computer in the order from 1 to n. Each block consists of m lines, k characters in each — the description of a layer in the format of an m × k table. Thus, the state of the CPU (x, y, z) is corresponded to the z-th character of the y-th line of the block number x. Character "1" corresponds to a working CPU and character "0" corresponds to a malfunctioning one. The blocks are separated by exactly one empty line.
第一行包含三个整数 n、m 和 k(1≤n,m,k≤100)——表示超级计算机的维度。
接下来是 n 个块,用于描述当前进程的状态。这些块按从第 1 层到第 n 层的顺序对应超级计算机的各层。每个块由 m 行组成,每行包含 k 个字符——即一个 m×k 表格形式的层描述。因此,CPU 坐标为 (x,y,z) 的状态对应于第 x 个块中第 y 行的第 z 个字符。“1” 表示该 CPU 正常工作,“0” 表示该 CPU 故障。各块之间恰好用一个空行分隔。
输出格式
Print a single integer — the number of critical CPUs, that is, such that turning only this CPU off will disrupt some control.
输出一个整数——关键 CPU 的数量,即仅关闭该 CPU 就会导致某些控制失效的 CPU 的数量。
输入输出样例
输入#1
2 2 3 000 000 111 111
输出#1
2
输入#2
3 3 3 111 111 111 111 111 111 111 111 111
输出#2
19
输入#3
1 1 10 0101010101
输出#3
0
说明/提示
In the first sample the whole first layer of CPUs is malfunctional. In the second layer when CPU (2, 1, 2) turns off, it disrupts the control by CPU (2, 1, 3) over CPU (2, 1, 1), and when CPU (2, 2, 2) is turned off, it disrupts the control over CPU (2, 2, 3) by CPU (2, 2, 1).
In the second sample all processors except for the corner ones are critical.
In the third sample there is not a single processor controlling another processor, so the answer is 0.
在第一个样例中,整个第一层的 CPU 均发生故障。在第二层中,当 CPU (2, 1, 2) 关闭时,它破坏了 CPU (2, 1, 3) 对 CPU (2, 1, 1) 的控制;而当 CPU (2, 2, 2) 关闭时,它破坏了 CPU (2, 2, 1) 对 CPU (2, 2, 3) 的控制。
在第二个样例中,除角落处的处理器外,其余所有处理器均为关键处理器。
在第三个样例中,不存在任何一个处理器控制另一个处理器的情况,因此答案为 0。
输入解题思路,AI测评打分。不知道怎么写?