2 shunfurh shunfurh 于 2017.01.14 14:47 提问

Food Cubes

Description

The spacemen in the space shuttle are waiting for the next escape window to return to the mother land Earth, where they are expected to fall somewhere in the deep blue waters of the Persian Gulf. Bored of waiting with nothing to do, they decide to play a game with their unit size food cubes. In the zero gravity environment of their spaceship, anything can stay motionless where it is placed. One spaceman places several food cubes in space such that there may be holes between cubes. Others, given the coordinates of the food cubes, should find the number of holes. A hole is a continuous empty space surrounded by food cubes in all six directions. You are to write a program to read the coordinates of each food cube and compute the number of holes.
Input

The first line of the input contains a single integer t (1 ≤ t ≤ 20) which is the number of test cases in the input. Each test case starts with an integer M, the number of food cubes. Each line i (1 ≤ i ≤ M) of the M following lines contains integers xi, yi and zi, all between 1 and 100 inclusive, indicating the three coordinates of a food cube in the 3D space.
Output

For each test case, there is one line containing the number of holes.
Sample Input

2
26
1 1 1
1 2 1
1 3 1
2 1 1
2 2 1
2 3 1
3 1 1
3 2 1
3 3 1
1 1 2
1 2 2
1 3 2
2 1 2
2 3 2
3 1 2
3 2 2
3 3 2
1 1 3
1 2 3
1 3 3
2 1 3
2 2 3
2 3 3
3 1 3
3 2 3
3 3 3
7
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
Sample Output

1
0

2个回答

caozhy
caozhy   Ds   Rxr 2017.01.22 00:47
已采纳
dabocaiqq
dabocaiqq   2017.01.21 22:58
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!