zoj 1788 Quad Trees

//#include "stdafx.h"
#include <string.h>
#include <string>
#include <queue>
#include <iostream>
#include "stdio.h"
using namespace std;
char MAP[512][512];
class quadtree// 
{
public:
	char value[3];// "00"->all 0 ,"01"->all 1,"1"->mixed
	quadtree*q[4];//four children
	quadtree()
	{
		q[0] = q[1] = q[2] = q[3] = 0;//initialize four children 
	}
	bool operator == (const quadtree &p)const// ，
	{
		if (strcmp(value, "1") == 0 || strcmp(value, p.value) != 0)
			return 0;
		else
			return 1;
	}

};
quadtree * DFS(int r, int c, int s)//r ,c  ，s 
{
	int i; bool f = 1;
	quadtree*temp = new quadtree;
	if (s==1)// ， 
	{
		temp->value[0] = '0';
		temp->value[1] =  MAP[r][c];
		temp->value[2] = 0;// ？
		return temp;

	}
	s /= 2;// 
	temp->q[0] = DFS(r, c, s);
	temp->q[1] = DFS(r, c + s, s);
	temp->q[2] = DFS(r + s, c, s);
	temp->q[3] = DFS(r + s, c + s, s);
	for (i = 1; i < 4;i++)
	{
		if(!(*temp->q[0] == *temp->q[i]))//some of four children are different ,can not be merged
		{
			f = 0;
			break;
		}
	}
	if (f)//all children are same,merge
	{
		strcpy(temp->value, temp->q[0]->value);
		for (i = 0; i < 4; i++)
			{
			delete temp->q[i]; temp->q[i] = 0;//delete all children 
			}
	}
	else// don't merge
	{
		strcpy(temp->value, "1");
	}
	return temp;
}
string BFS(quadtree*root)// ， 
{
	string s = "";
	quadtree *cur = root;
	queue <quadtree*> que;
	que.push(root);
	while (!que.empty())
	{
		cur = que.front();
		que.pop();
		s += cur->value;
		for (int i = 0; i < 4; i++)
		{
			if (cur->q[i]->value != NULL)// ！！！！！！！
			que.push(cur->q[i]);
		}
	}
	return s;
}
//////////////////////////////////////////////
// 16 。。 
char tohex(const string& str)
{
	int ret = 0;

	for (int i = 0; i < 4; i++) 
	{
		ret <<= 1;//   16 
		if (str[i] == '1')
			++ret;
	}

	return (ret < 10) ? '0' + ret : 'A' + ret - 10;
}
string ToHex(const string& str)
{
	string tmp = str;
	string ret = "";

	while (tmp.length() % 4 != 0)
		tmp = "0" + tmp;
	for (size_t i = 0; i < tmp.length(); i += 4)
		ret += tohex(tmp.substr(i, 4));//substr  ，i ，4 

	return ret;
}
////  = =
///////////////////////////////////////////////////
int  main()
{
	string al;
	int k, N;
	scanf("%d", &k);// test  
	while (k--)
	{
		scanf("%d", &N);
		for (int i = 0; i < N; i++)// 
		{
			for (int  j = 0; j < N; j++)
			{
				cin >> MAP[i][j];// scanf("%c", &MAP[i][j]);//initialize the array
				
			}
	
		}
		quadtree *root;
		root =DFS(0, 0, N);//build a quardtree;
		al = BFS(root);
		//cout << al << endl;
		cout << ToHex(al) << endl;
	}
	return 0;
}