pku2882.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

/***********************************
	
	Author:		Sempr
	Algorithm:	BFS
	Date:		2006-07-16

***********************************/

#include <stdio.h>
#include <string.h>
#define size 105

typedef struct Point
{
	int x, y, z;
} Point;

const int F[6][3] = {
	{ 1, 0, 0}, {0,  1, 0}, {0, 0,  1},
	{-1, 0, 0}, {0, -1, 0}, {0, 0, -1}
};

char m[size][size][size], v[size][size][size];
int Xmax, Ymax, Zmax, Xmin, Ymin, Zmin;
Point Q[size * size * size / 12];

int Min(int a, int b)
{
	return a < b ? a : b;
}

int Max(int a, int b)
{
	return a > b ? a : b;
}

int In(int x, int y, int z)
{
	return x >= Xmin && x <= Xmax && y >= Ymin && y <= Ymax && z >= Zmin && z <= Zmax;
}

int BFS(int x, int y, int z)
{
	int nx, ny, nz;
	int i;
	int Q_head, Q_tail;
	int res = 1;
	Q_head = 0;
	Q_tail = 1;
	Q[0].x = x;
	Q[0].y = y;
	Q[0].z = z;
	v[x][y][z] = 1;
	while (Q_head < Q_tail)
	{
		x = Q[Q_head].x;
		y = Q[Q_head].y;
		z = Q[Q_head].z;
		for (i = 0; i < 6; i++)
		{
			nx = x + F[i][0];
			ny = y + F[i][1];
			nz = z + F[i][2];
			if (!In(nx, ny, nz))
			{
				res = 0;
				continue;
			}
			if (v[nx][ny][nz] || m[nx][ny][nz])
				continue;
			v[nx][ny][nz] = 1;
			Q[Q_tail].x = nx;
			Q[Q_tail].y = ny;
			Q[Q_tail].z = nz;
			Q_tail++;
		}
		Q_head++;
	}
	return res;
}

void Solve()
{
	int i, j, k;
	int x, y, z;
	int M, cnt;
	memset(m, 0, sizeof(m));
	memset(v, 0, sizeof(v));
	scanf("%d", &M);

	Xmax = 0;
	Ymax = 0;
	Zmax = 0;
	Xmin = 110;
	Ymin = 110;
	Zmin = 110;
	
	for (i = 0; i < M; i++)
	{
		scanf("%d %d %d", &x, &y, &z);
		Xmax = Max(Xmax, x);
		Ymax = Max(Ymax, y);
		Zmax = Max(Zmax, z);

		Xmin = Min(Xmin, x);
		Ymin = Min(Ymin, y);
		Zmin = Min(Zmin, z);

		m[x][y][z] = 1;
	}

	cnt = 0;
	for (i = Xmin; i <= Xmax; i++)
	{
		for (j = Ymin; j <= Ymax; j++)
		{
			for (k = Zmin; k <= Zmax; k++)
			{
				if (m[i][j][k] == 0 && v[i][j][k] == 0)
					cnt += BFS(i, j, k);
			}
		}
	}
	printf("%d\n", cnt);
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
		Solve();
	return 0;
}