盒子（Box,UVa1587）(算法竞赛入门经典习题3-10)C++

题目：给定6个矩形的长和宽w、h（w>=1,h<=1000）,判断它们能否构成长方体的六个面。

思路：本题解采用较暴力的解法，不考虑是几边的情况，注意长宽的三点即可。结合长方体面的特性，第一，长方体是由三对相同的面构成的，因此首先要判断输入的六组矩形是否满足两两相等。第二，长方体的各个面会与相邻的面有接壤，要判断是否不同组矩形有相同的数据。第三，每个长方体由长宽高组成，因此每个边将出现三次（如果是特殊情况，将出现三次以上，比如正方体）。

结合这三点，依次判断出来，最后看是否全都满足决定是否可以构成长方体。

已通过vj测试！

#include
using namespace std;
int w[6], h[6];

int main()
{
	while (cin>>w[0]>>h[0])
	{
		int flag = 1;
		int count = 0;
		int num1 = 0;
		int num2 = 0;
		int a = -1, b = -1, c = -1, d = -1;      //标记已配对过的，ab一组，cd一组
		for (int i = 1; i < 6; i++)
		{
			cin >> w[i] >> h[i];
		}
		for (int j = 0; j < 6; j++)              //是否有三对相同的面
		{
			if (j == a || j == b || j == c || j == d)
				continue;
			for (int k = 0; k < 6; k++)
			{
				if (k == a || k == b || k == c || k == d || k == j)
					continue;
				if ((w[j] == w[k] && h[j] == h[k]) || (w[j] == h[k] && h[j] == w[k]))
				{
					count++;
					if (a == -1)
					{
						a = j;
						b = k;
						break;
					}
					if (c == -1)
					{
						c = j;
						d = k;
						break;
					}
					break;
				}
			}
		}
		count--;
		for(int m=0;m<6;m++)                     //是否每个面都有与其他面接壤
			for(int n=m+1;n<6;n++)
				if (w[m] != w[n] && w[m] != h[n] && h[m] != w[n] && h[m] != h[n])
				{
					flag = 0;
					break;
				}
		for (int o = 0; o < 6; o++)              //是否每个边出现三次或以上
		{
			num1 = 0;
			num2 = 0;
			for (int p = 0; p < 6; p++)
			{
				if (o == p)
					continue;
				if (w[o] == w[p] || w[o] == h[p])
					num1++;
				if (h[o] == h[p] || h[o] == w[p])
					num2++;
			}
			if (num1 < 3 || num2 < 3)
			{
				flag = 0;
				break;
			}
		}
		if (count == 3 && flag == 1)
			cout << "POSSIBLE" << endl;
		else
			cout << "IMPOSSIBLE" << endl;
	}
	return 0;
}

望指正！