首页 > ACM题库 > HDU-杭电 > HDU 2762-HOJ-Area of Polycubes[解题报告]C++
2014
02-14

HDU 2762-HOJ-Area of Polycubes[解题报告]C++

Area of Polycubes

问题描述 :

A polycube is a solid made by gluing together unit cubes (one unit on each edge) on one or more faces. The figure in the lower-left is not a polycube because some cubes are attached along an edge.

For this problem, the polycube will be formed from unit cubes centered at integer lattice points in 3-space. The polycube will be built up one cube at a time, starting with a cube centered at (0,0,0). At each step of the process (after the first cube), the next cube must have a face in common with a cube previously included and not be the same as a block previously included. For example, a 1-by-1-by-5 block (as shown above in the upper-left polycube) could be built up as:

(0,0,0) (0,0,1) (0,0,2) (0,0,3) (0,0,4)

and a 2-by-2-by-2 cube (upper-right figure) could be built as:

(0,0,0) (0,0,1) (0,1,1) (0,1, 0) (1,0,0) (1,0,1) (1,1,1) (1,1, 0)

Since the surface of the polycube is made up of unit squares, its area is an integer.

Write a program which takes as input a sequence of integer lattice points in 3-space and determines whether is correctly forms a polycube and, if so, what the surface area of the polycube is.

输入:

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of data sets that follow. Each data set consists of multiple lines of input. The first line contains the number of points P, (1 ≤ P ≤ 100) in the problem instance. Each succeeding line contains the centers of the cubes, eight to a line (except possibly for the last line). Each center is given as 3 integers, separated by commas. The points are separated by a single space.

输出:

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of data sets that follow. Each data set consists of multiple lines of input. The first line contains the number of points P, (1 ≤ P ≤ 100) in the problem instance. Each succeeding line contains the centers of the cubes, eight to a line (except possibly for the last line). Each center is given as 3 integers, separated by commas. The points are separated by a single space.

样例输入:

4 
5 
0,0,0 0,0,1 0,0,2 0,0,3 0,0,4 
8 
0,0,0 0,0,1 0,1,0 0,1,1 1,0,0 1,0,1 1,1,0 1,1,1
4 
0,0,0 0,0,1 1,1,0 1,1,1 
20 
0,0,0 0,0,1 0,0,2 0,1,2 0,2,2 0,2,1 0,2,0 0,1,0
1,0,0 2,0,0 1,0,2 2,0,2 1,2,2 2,2,2 1,2,0 2,2,0
2,1,0 2,1,2 2,0,1 2,2,1 

样例输出:

1 22 
2 24 
3 NO 3 
4 72 

没有看网上别的解题报告,直接O(n^2)的时间复杂度,倒也直接accept了。

对每个新加入的方块,考虑其与之前的每个方块的“距离”,如果为0,则不正确(因为重叠了);如果遍历完了,没有一个为1的,则也不正确(与之前的连不起来)。否则,正确。

对两点之间距离的定义,这里应该是个欧几里德距离,但是考虑到我们只考虑是否为0或1,因而将坐标之差绝对值相加即可,运算相对简单些。

代码如下:

// Area of Polycubes

#include <iostream>
using namespace std;

const int MAXP = 100;

int dis(int *p1, int *p2)
{
	int d = 0;
	for(int i = 0; i < 3; ++i)
	{
		d += abs(p1[i] - p2[i]);
	}
	return d;
}

int main()
{
	int N;
	cin>>N;
	int points[MAXP][3];
	for(int no = 0; no < N; ++no)
	{
		int P;
		cin>>P;
		
		fscanf(stdin, "%d,%d,%d", &points[0][0], &points[0][1], &points[0][2]);
		int area = 6;
		bool iscorrect = true;

		cout<<no + 1<<" ";
		for(int i = 1; i < P; ++i)
		{
			fscanf(stdin, "%d,%d,%d", &points[i][0], &points[i][1], &points[i][2]);
			if(!iscorrect)
			{
				continue;
			}

			area += 6;

			int j = 0;
			bool isconnected = false;
			while(j < i)
			{
				int d = dis(points[i], points[j]);

				if(d == 0)
				{
					break;
				}

				if(d == 1)
				{
					isconnected = true;
					area -= 2;
				}

				j++;
			}
			if(j != i || !isconnected)
			{
				iscorrect = false;
				cout<<"NO "<<i + 1<<endl;
			}
		}
		if(iscorrect)
		{
			cout<<area<<endl;
		}
	}
	return 0;
}

解题参考:http://blog.csdn.net/thestoryofsnow/article/details/11882277


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。