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      2017.01.22 00:47

dabocaiqq   2017.01.21 22:58

soj 1114. Food Cubes

Sicily 1114 Food Cubes

1114 Food Cubes
<br />TAG 种子染色  Flood Fill<br />忙于课程的各种projects，好久没写acm，惭愧，写个简单的种子染色都搞得焦头烂额。哎。<br />3维的跟2维的处理起来没多大区别。<br />不过直接深度优先居然stack overflow。才 10^6啊！？<br />所以先求出坐标的取值范围，然后扩大1个单位。最后答案要减1，也就是包围food的那个空间。<br />#include <stdio.h> #include <memory.h> const int N=102;
Sicily.1114 Food Cubes

1114. Food Cubes
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 emp

Codeforces 520D. Cubes 状态模拟+贪心
Codeforces 520D Description Once Vasya and Petya assembled a figure of m cubes, each of them is associated with a number between 0 and m - 1 (inclusive, each number appeared exactly once
OpenGL笔记——Marching cubes算法
Poisson Surface Reconstruction
Marching Cubes
MarchingCubes建模是三维可视化库VTK建模算法之一。该建模方法采用空间分解的方法，对空间体元进行不断的切割处理，最后得到一个由规则体构成的非规则复杂物体的近似。这种方法包括有物体的内在信息，从而实现体数据的表达。 MC方法求等值面的算法流程： ① 将三维离散规则数据场分层读入内存； ② 扫描两层数据，逐个构造体元，每个体元中的8个角点取自相邻的两层； ③ 将体元每个角点