QUADTREE

https://algospot.com/judge/problem/read/QUADTREE

algospot.com :: QUADTREE

기존 쿼드트리     : 0 -> 1 -> 2 -> 3

상하반전 쿼드트리 : 2 -> 3 -> 0 -> 1

#define SIZE 32

typedef struct leaf{
	int depth;
	char value;

	leaf *parent;
	leaf *child[4];
}QTREE;

bool MAP[SIZE][SIZE];
int CARD[4] = { 2, 3, 0, 1 };
int POW(int N)
{
	int H = 1;
	for (int i = 0; i < N; i++)
		H *= 2;
	return H;
}
void MakeLeaf(leaf *CurLeaf, int &peek, char *Data)
{
	if (CurLeaf->depth == -1)
	{
		CurLeaf->depth = 0;
		CurLeaf->value = Data[peek++];
		if (CurLeaf->value == 'x')
			MakeLeaf(CurLeaf, peek, Data);
	}
	else
	{
		for (int i = 0; i < 4; i++)
		{
			leaf* t = (leaf*) malloc(sizeof(leaf));
			t->parent = CurLeaf;
			t->depth = CurLeaf->depth + 1;
			t->value = Data[peek++];
			if (t->value == 'x')
				MakeLeaf(t, peek, Data);
			CurLeaf->child[i] = t;
		}
	}
}
void PrintQTREE(leaf *ROOT)
{
	printf("%c", ROOT->value);
	if (ROOT->value == 'x')
		for (int i = 0; i < 4; i++)
		{
			if (ROOT->child[i]->value == 'x')
				PrintQTREE(ROOT->child[i]);
			else
				printf("%c", ROOT->child[i]->value);
		}

	if (ROOT->parent == NULL)
		printf("\n");
}
void PrintQTREE2(leaf *ROOT)
{
	printf("%c", ROOT->value);
	if (ROOT->value == 'x')
		for (int j = 0; j < 4; j++)
		{
			int i = CARD[j];

			if (ROOT->child[i]->value == 'x')
				PrintQTREE2(ROOT->child[i]);
			else
				printf("%c", ROOT->child[i]->value);
		}

	if (ROOT->parent == NULL)
		printf("\n");
}
void FillMap(leaf* ROOT, int sX, int sY)
{
	int length = SIZE / POW(ROOT->depth);
	if (ROOT->value == 'x')
	{
		for (int i = 0; i < 4; i++)
			FillMap(ROOT->child[i], sX + (i % 2 * length / 2), sY + (i / 2 * length / 2));
	}
	else
	{
		for (int i = sY; i < sY + length; i++)
			for (int j = sX; j < sX + length; j++)
				MAP[i][j] = (ROOT->value == 'b') ? 1 : 0;
	}
}
void PrintMAP()
{
	for (int i = 0; i < SIZE; i++){
		for (int j = 0; j < SIZE; j++)
			(MAP[i][j]) ? printf("1") : printf("0");
		printf("\n");
	}
}
void ReverseMAP()
{
	for (int i = 0; i < SIZE / 2; i++)
	{
		bool BUF[SIZE];
		memcpy(BUF, MAP[i], SIZE);
		memcpy(MAP[i], MAP[SIZE - i - 1], SIZE);
		memcpy(MAP[SIZE - i - 1], BUF, SIZE);
	}
}
void MAP2QTREE(leaf* ROOT, int sX, int sY)
{
	int length = SIZE / POW(ROOT->depth) / 2;
	bool PLAG = MAP[sY][sX];

	if (MAP[sY + length][sX] == PLAG &&
		MAP[sY][sX + length] == PLAG &&
		MAP[sY + length][sX + length] == PLAG)
		ROOT->value = (PLAG) ? 'b' : 'w';
	else
	{
		ROOT->value = 'x';
		for (int i = 0; i < 4; i++)
		{
			leaf* t = (leaf*) malloc(sizeof(leaf));
			t->parent = ROOT;
			t->depth = ROOT->depth + 1;
			ROOT->child[i] = t;
			MAP2QTREE(t, sX + (i % 2 * length), sY + (i / 2 * length));
		}
	}
}
void DeleteQTree(leaf* ROOT)
{
	if (ROOT->value == 'x')
	{
		for (int i = 0; i < 4; i++)
			DeleteQTree(ROOT->child[i]);
	}
	else
		free(ROOT);
}
int main()
{
	int T;
	for (scanf("%d", &T); T > 0; T--)
	{
		char BUF[1001];
		int BUF_index = 0, peek = 0;
		QTREE *head, *head2;
		memset(MAP, 0, sizeof(MAP));

		head = (leaf*) malloc(sizeof(leaf));
		head->parent = NULL;
		head->depth = -1;

		scanf("%s", &BUF);

		MakeLeaf(head, peek, BUF);

		//PrintQTREE(&head);

		//FillMap(head, 0, 0);

		//PrintMAP();
		//ReverseMAP();

		PrintQTREE2(head);
		
		//head2 = (leaf*) malloc(sizeof(leaf));
		//head2->parent = NULL;
		//head2->depth = 0;
		//MAP2QTREE(head2, 0, 0);

		//PrintQTREE(head2);

		DeleteQTree(head);
		//DeleteQTree(head2);
	}
	return 0;
}