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.


-----Input-----

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.


-----Output-----

Print a single integer — the number of critical CPUs, that is, such that turning only this CPU off will disrupt some control.


-----Examples-----
Input
2 2 3
000
000

111
111

Output
2

Input
3 3 3
111
111
111

111
111
111

111
111
111

Output
19

Input
1 1 10
0101010101

Output
0



-----Note-----

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.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Complete search


Solutions:
def safe(pos):
	return pos[0] >= 0 and pos[0] < n and (pos[1] >= 0) and (pos[1] < m) and (pos[2] >= 0) and (pos[2] < p)

def CPU_status(pos, number):
	return safe(pos) and super_computer[pos[0]][pos[1]][pos[2]] == number

def critical(x, y, z):
	if super_computer[x][y][z] != '0':
		current = [x, y, z]
		for i in range(3):
			parent = current.copy()
			parent[i] -= 1
			if CPU_status(parent, '1'):
				for j in range(3):
					(child, alt) = (current.copy(), parent.copy())
					child[j] += 1
					alt[j] += 1
					if CPU_status(child, '1') and (CPU_status(alt, '0') or j == i):
						return 1
	return 0
(n, m, p) = map(int, input().split())
(super_computer, crit) = ([], 0)
for i in range(n):
	super_computer.append([input() for _ in range(m)])
	if i != n - 1:
		input()
for i in range(n):
	for j in range(m):
		for k in range(p):
			crit += critical(i, j, k)
print(crit)


def put():
	return map(int, input().split())

def safe(x, y, z):
	return x >= 0 and y >= 0 and (z >= 0) and (x < n) and (y < m) and (z < p)

def check(x, y, z):
	if mat[x][y][z] == '0':
		return 0
	cur = [x, y, z]
	for i in range(3):
		src = cur.copy()
		src[i] -= 1
		if not safe(src[0], src[1], src[2]) or mat[src[0]][src[1]][src[2]] == '0':
			continue
		for j in range(3):
			des = cur.copy()
			des[j] += 1
			alt = src.copy()
			alt[j] += 1
			if safe(des[0], des[1], des[2]) and mat[des[0]][des[1]][des[2]] == '1':
				if j == i:
					return 1
				elif safe(alt[0], alt[1], alt[2]) and mat[alt[0]][alt[1]][alt[2]] == '0':
					return 1
	return 0
(n, m, p) = put()
mat = []
ans = 0
for i in range(n):
	mat.append([input() for j in range(m)])
	if i != n - 1:
		input()
for i in range(n):
	for j in range(m):
		for k in range(p):
			ans += check(i, j, k)
print(ans)


def func(i, j, t):
	if i > 0:
		if A[i - 1][j][t] == '1':
			if i < n - 1:
				if A[i + 1][j][t] == '1':
					return True
			if j < m - 1:
				if A[i][j + 1][t] == '1' and A[i - 1][j + 1][t] == '0':
					return True
			if t < k - 1:
				if A[i - 1][j][t + 1] == '0' and A[i][j][t + 1] == '1':
					return True
	if j > 0:
		if A[i][j - 1][t] == '1':
			if j < m - 1:
				if A[i][j + 1][t] == '1':
					return True
			if i < n - 1:
				if A[i + 1][j][t] == '1' and A[i + 1][j - 1][t] == '0':
					return True
			if t < k - 1:
				if A[i][j - 1][t + 1] == '0' and A[i][j][t + 1] == '1':
					return True
	if t > 0:
		if A[i][j][t - 1] == '1':
			if t < k - 1:
				if A[i][j][t + 1] == '1':
					return True
			if i < n - 1:
				if A[i + 1][j][t] == '1' and A[i + 1][j][t - 1] == '0':
					return True
			if j < m - 1:
				if A[i][j + 1][t - 1] == '0' and A[i][j + 1][t] == '1':
					return True
	return False
(n, m, k) = list(map(int, input().split()))
A = [0] * n
for i in range(n):
	A[i] = [0] * m
	for j in range(m):
		A[i][j] = [0] * k
for i in range(n):
	for j in range(m):
		per = input()
		for t in range(k):
			A[i][j][t] = per[t]
	if i != n - 1:
		per = input()
answer = 0
for i in range(n):
	for j in range(m):
		for t in range(k):
			if A[i][j][t] == '1':
				if func(i, j, t):
					answer += 1
print(answer)


(n, m, k) = (int(z) for z in input().split())
M = []
for i in range(n):
	for j in range(m):
		s = input()
		for p in range(len(s)):
			M += [int(s[p])]
	if i != n - 1:
		s = input()
res = 0
cur = 0
for i in range(n):
	for j in range(m):
		for h in range(k):
			if M[cur] == 1:
				if 1 <= i <= n - 2 and M[cur - m * k] + M[cur + m * k] == 2:
					res += 1
				elif 1 <= h <= k - 2 and M[cur - 1] + M[cur + 1] == 2:
					res += 1
				elif 1 <= j <= m - 2 and M[cur - k] + M[cur + k] == 2:
					res += 1
				elif h <= k - 2 and j >= 1 and (M[cur + 1] + M[cur - k] == 2) and (M[cur - k + 1] == 0):
					res += 1
				elif j <= m - 2 and h >= 1 and (M[cur - 1] + M[cur + k] == 2) and (M[cur + k - 1] == 0):
					res += 1
				elif h <= k - 2 and i >= 1 and (M[cur + 1] + M[cur - m * k] == 2) and (M[cur - m * k + 1] == 0):
					res += 1
				elif i <= n - 2 and h >= 1 and (M[cur - 1] + M[cur + m * k] == 2) and (M[cur + m * k - 1] == 0):
					res += 1
				elif i <= n - 2 and j >= 1 and (M[cur - k] + M[cur + m * k] == 2) and (M[cur + m * k - k] == 0):
					res += 1
				elif j <= m - 2 and i >= 1 and (M[cur + k] + M[cur - m * k] == 2) and (M[cur - m * k + k] == 0):
					res += 1
			cur += 1
print(res)


def check(d, i, j, l):
	global result, save
	if d[i][j][l] == 1:
		if d[i + 1][j][l] == 1 and d[i - 1][j][l] == 1:
			result += 1
			return
		if d[i][j + 1][l] == 1 and d[i][j - 1][l] == 1:
			result += 1
			return
		if d[i][j][l + 1] == 1 and d[i][j][l - 1] == 1:
			result += 1
			return
		if d[i - 1][j + 1][l] == 0 and d[i][j + 1][l] == 1 and (d[i - 1][j][l] == 1):
			result += 1
			return
		if d[i][j + 1][l - 1] == 0 and d[i][j + 1][l] == 1 and (d[i][j][l - 1] == 1):
			result += 1
			return
		if d[i + 1][j][l - 1] == 0 and d[i + 1][j][l] == 1 and (d[i][j][l - 1] == 1):
			result += 1
			return
		if d[i + 1][j - 1][l] == 0 and d[i + 1][j][l] == 1 and (d[i][j - 1][l] == 1):
			result += 1
			return
		if d[i][j - 1][l + 1] == 0 and d[i][j - 1][l] == 1 and (d[i][j][l + 1] == 1):
			result += 1
			return
		if d[i - 1][j][l + 1] == 0 and d[i - 1][j][l] == 1 and (d[i][j][l + 1] == 1):
			result += 1
			return
(n, m, k) = map(int, input().split())
d = [[[0] * (k + 2) for i in range(m + 2)] for j in range(n + 2)]
for i in range(1, n + 1):
	for j in range(1, m + 1):
		st = input()
		for l in range(k):
			d[i][j][l + 1] = int(st[l])
	if i != n:
		a = input()
result = 0
for i in range(1, n + 1):
	for j in range(1, m + 1):
		for l in range(1, k + 1):
			check(d, i, j, l)
print(result)


def main():
	s = input().split()
	(n, m, k) = (int(s[0]), int(s[1]), int(s[2]))
	processor = []
	for x in range(n):
		for y in range(m):
			s = input()
			for z in s:
				processor.append(int(z) == 1)
		if x < n - 1:
			emptyLine = input()
	counter = 0
	mk = m * k
	nmk = n * mk
	for i in range(nmk):
		if not processor[i]:
			continue
		if i >= mk:
			if processor[i - mk]:
				if i < nmk - mk:
					if processor[i + mk]:
						counter += 1
						continue
				if i % k < k - 1:
					if processor[i + 1]:
						if not processor[i - mk + 1]:
							counter += 1
							continue
				if i % mk < mk - k:
					if processor[i + k]:
						if not processor[i - mk + k]:
							counter += 1
							continue
		if i % k > 0:
			if processor[i - 1]:
				if i < nmk - mk:
					if processor[i + mk]:
						if not processor[i + mk - 1]:
							counter += 1
							continue
				if i % k < k - 1:
					if processor[i + 1]:
						counter += 1
						continue
				if i % mk < mk - k:
					if processor[i + k]:
						if not processor[i + k - 1]:
							counter += 1
							continue
		if i % mk >= k:
			if processor[i - k]:
				if i < nmk - mk:
					if processor[i + mk]:
						if not processor[i + mk - k]:
							counter += 1
							continue
				if i % k < k - 1:
					if processor[i + 1]:
						if not processor[i - k + 1]:
							counter += 1
							continue
				if i % mk < mk - k:
					if processor[i + k]:
						counter += 1
						continue
	print(counter)
main()