U E D R , A S I H C RSS

Tower Of Cubes/조현태

No older revisions available

No older revisions available



설명 및 느낀점


박스놀이.. 왜이렇게 답이 많은거야..T.T
검증의 귀차니즘.ㅋ
이번엔 전역변수 안썼으나.. 안의 구조체 전달을 포인터 전달로 변환하면 속도 향상할 수 있음 ^^;

소스코드


~cpp
#include <iostream>
#include <vector>

using namespace std;

const char DEBUG_READ[] = "3\n1 2 2 2 1 2\n3 3 3 3 3 3\n3 2 1 1 1 1\n10\n1 5 10 3 6 5\n2 6 7 3 6 9\n5 7 3 2 1 9\n1 3 3 5 8 10\n6 6 2 2 4 4\n1 2 3 4 5 6\n10 9 8 7 6 5\n6 1 2 3 4 7\n1 2 3 3 2 1\n3 2 1 1 2 3\n0";
const int BOX_FACE_NUMBER = 6;
const char FACE_NAME[BOX_FACE_NUMBER][7] = {"front", "back", "left", "right", "top", "bottom"};
const int FRONT = 0;
const int BACK = 1;
const int LEFT = 2;
const int RIGHT = 3;
const int TOP = 4;
const int BOTTOM = 5;

struct SMyBox {
	SMyBox(int front, int back, int left, int right, int top, int bottom)
	{
		color[FRONT] = front;
		color[BACK] = back;
		color[LEFT] = left;
		color[RIGHT] = right;
		color[TOP] = top;
		color[BOTTOM] = bottom;
	}
	int color[BOX_FACE_NUMBER];
};

struct SBoxBlock
{
	SBoxBlock(int inputNumber, int inputTopFace)
	{
		number = inputNumber;
		topFace = inputTopFace;
	}
	int number;
	int topFace;
};

const char* AddBox(const char* readData, vector<SMyBox*>& myBoxs)
{
	int front, back, left, right, top, bottom;
	sscanf(readData, "%d %d %d %d %d %d", &front, &back, &left, &right, &top, &bottom);
	myBoxs.push_back(new SMyBox(front, back, left, right, top, bottom));
	//printf("%2d %2d %2d %2d %2d %2d\n", front, back, left, right, top, bottom);
	return strchr(readData, '\n') + 1;
}

inline int GetOppositeFace(int faceNumber)
{
	if (1 == faceNumber % 2)
		return faceNumber - 1;
	return faceNumber + 1;
}

void SuchNextBox(vector<SMyBox*>& myBoxs, int boxNumber, int lastColor, vector<SBoxBlock>& myBoxStack, vector<SBoxBlock>& bestHeight)
{
	//// 박스가 가장 작은것까지 쌓였을때. ////
	if (0 > boxNumber)
	{
		if (myBoxStack.size() > bestHeight.size())
		{
			bestHeight = myBoxStack;
		}
		return;
	}

	vector<int> suchFaceList;
	suchFaceList.reserve(BOX_FACE_NUMBER);
	//// 밑바닥의 면과 색상이 같은 면을 찾아낸다. ////
	if (0 == lastColor)
	{
		for (register int i = 0; i < BOX_FACE_NUMBER; ++i)
			suchFaceList.push_back(i);
	}
	else
	{
		for (register int i = 0; i < BOX_FACE_NUMBER; ++i)
		{
			if (lastColor == myBoxs[boxNumber]->color[i])
			{
				suchFaceList.push_back(GetOppositeFace(i));
			}
		}
	}
	//// 맞는 면이 없을때. ////
	if (0 == suchFaceList.size())
	{
		if (myBoxStack.size() > bestHeight.size())
		{
			bestHeight = myBoxStack;
		}
		return;
	}
	
	//// 다른 상자를 올려봅니다. ////
	for (register int i = 0; i < (int)suchFaceList.size(); ++i)
	{
		myBoxStack.push_back(SBoxBlock(boxNumber, suchFaceList[i]));
		for (register int j = boxNumber - 1; j >= -1 ; --j)
		{
			SuchNextBox(myBoxs, j, myBoxs[boxNumber]->color[suchFaceList[i]], myBoxStack, bestHeight);
		}
		myBoxStack.pop_back();
	}
}

void ShowBoxStack(vector<SBoxBlock>& showStack)
{
	cout << showStack.size() << endl;
	for (register int i = (int)showStack.size() - 1; i >= 0 ; --i)
	{
		cout << showStack[i].number + 1 << " ";
		cout << FACE_NAME[showStack[i].topFace] << endl;
	}
}

void FreeMemory(vector<SMyBox*>& myBoxs)
{
	for (register int i = 0; i < (int)myBoxs.size(); ++i)
	{
		delete myBoxs[i];
	}
}

void main()
{
	int boxNumber = 0;
	const char* readData = DEBUG_READ;
	for (int caseNumber = 1; ; ++caseNumber)
	{
		sscanf(readData, "%d", &boxNumber);
		readData = strchr(readData, '\n') + 1;

		if (0 == boxNumber)	//예쁜 상자가 없으면 종료한다 -ㅡV
			break;

		vector<SMyBox*> myBoxs;
		for (register int i = 0; i < boxNumber; ++i)
		{
			readData = AddBox(readData, myBoxs);
		}
		
		vector<SBoxBlock> myBoxStack;
		vector<SBoxBlock> bestStack;
		SuchNextBox(myBoxs, (int)myBoxs.size() - 1, 0, myBoxStack, bestStack);
		cout << "Case #" << caseNumber << endl;
		ShowBoxStack(bestStack);
		FreeMemory(myBoxs);
		cout << endl;
		
	}
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0141 sec