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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
soj 1114. Food Cubes
题意: 在100*100*100的三维空间内,给出若干食物的坐标,如果一段空间被食物包围着,那么这段空间就成为一个洞,求洞的数目 思路: 对每一个不是食物的点做bfs的Flood Fill即可。(还有一种方法是对每一个是食物的点做dfs的Flood Fill,不过想想看如果是2,2,2到99,99,99是一个洞的话,这个洞的表面积,大约100*100*6 = 60000,爆栈吧,没尝试过)
Sicily 1114 Food Cubes
广度优先搜索在三维空间上的扩展,题目本身难度不大,但是在写的时候有个判断条件没有考虑仔细,多刷了好几次提交,几乎崩溃。 #include #include #include using namespace std; int data[105][105][105]; bool is_valid( int x, int y, int z ) { if ( x>=0&&x=0&&y=0&
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
三维空间上的BFS。(不是自己想出来的,思路是讨论区@TLE from SMIE 同学的。) 需要注意的地方:1.hole不一定是一个点,注意到关键词:continuous ,它可以是任意形状的,只要六个方向都 被围住即可。 2.一定要考虑到边界,即"hole"若有一部分是边界,那它便不是hole。 代码如下: #include #include using namespace
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
球体的Marching Cubes实现
球体的Marching Cubes实现
一个极简的Marching Cubes算法实现
从网上down了一个MC算法代码,发现里面还是有很多冗余代码,经过删除,修改,实现了一个极简单的MC算法实现,可以绘制三角面片模拟等值面,供初学者参考,完整代码贴出: #include #include #include #include // GLu32 Library的头文件 //对于每一条边,如果一个顶点在边界内而另一个顶点在边界外,那么这条边和边界肯定有
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个角点取自相邻的两层; ③ 将体元每个角点